CODEWITHSUNDEEP
java
ik024
ik024

Reputation: 3596

Computing number of squares between two numbers, works only with small numbers, why?

The problem is to find the numbers of squares between two numbers.

The code below works small numbers but fails for huge numbers. How can I correct this?

 import java.io.*;
 import java.util.*;
 import java.text.*;
 import java.math.*;
 import java.util.regex.*;

 public class NumOfSqrs {


public static void main(String[] args) {

    try{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String input;
    int line = 0;
    int testCases;
    int numOfSqrt = 0;      
    int j = 0;  

    while((input=br.readLine())!=null){

        if(line == 0){
          testCases = Integer.parseInt(input);
          line = line +1;
        }
        else{
          String[] splitter = input.toString().split(" ");

          //Here splitter gives two numbers, we need to find no of sqrs b/w these numbers for eg say 3 and 9

           for(int i = Integer.parseInt(splitter[0]); i<=Integer.parseInt(splitter[1]) ; i++){

            String value = ""+Math.sqrt(i);
            String[] isSqrt = value.toString().split("\\.");
            //System.out.println(""+isSqrt[0] + "" + isSqrt[1]);

            //Here lets say if  'i' is 4 (i.e 2.0) then isSqrt[0] = 2, isSqrt[1] = 0 and if isSqrt[1] != 1 then its obvious that its not a perfect square

            if(isSqrt[1].length() == 1){
              numOfSqrt++;
            }

          }
          System.out.println(""+numOfSqrt);
        }
     numOfSqrt = 0;
    }


    }catch(IOException io){
        io.printStackTrace();
    }   


  }
}

Upvotes: 3

Views: 4121

Answers (3)

Tarek Khalil
Tarek Khalil

Reputation: 415

This is a simpler algorithm, and it works up to 100,000,000 relatively fast.

int low = 1, high = 100000000;
int max = 0;
int count = 0;

for (int j = low; j <= high; j++)
{
    while (max * max < j)
        max++;

    if (max * max == j)
        Console.WriteLine(max * max);
}

Upvotes: 1

Bohemian
Bohemian

Reputation: 425208

Your technique for determining squares (converting to String and splitting on dot) is dodgy.

It's also unnecessary - you can use purely numeric approach in just one line:

int low, high; // fill from input
int numOfSqrt = (int) (Math.floor(Math.sqrt(high)) - Math.ceil(Math.sqrt(low)) + 1);

Upvotes: 13

RKC
RKC

Reputation: 1874

I will suggest to find the square root the first number given in the input ,let us take it as 10 and the square root will be like 3.(some thing) now take 4 and check whether 16 is in the range and like that for 5 check whether 25 is in the range and so on.

Upvotes: 0

Related Questions