Interview Questions

Perfect Squares - Sherlock and Squares

Problem Statement

Sherlock and Squares


Watson gives two integers ( and ) to Sherlock and asks if he can count the number of square integers between and (both inclusive).

Note: A square integer is an integer which is the square of any integer. For example, 1, 4, 9, and 16 are some of the square integers as they are squares of 1, 2, 3, and 4, respectively.

Input Format
The first line contains , the number of test cases. test cases follow, each in a new line.
Each test case contains two space-separated integers denoting and .

Output Format
For each test case, print the required answer in a new line.

Constraints

Sample Input

2
3 9
17 24

Sample output

2
0

Explanation
Test Case #00: In range , and are the two square numbers.
Test Case #01: In range , there are no square numbers.

import java.util.Scanner;
/*
 * The difference between two perfect squares a,b is
 * b = a + (2 * (sqrt(b))+1
 * for example, a=9,b=16
 * 16 = 9 + (2 * 3) + 1
 */

public class Solution {

    public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i=0;i<N;i++)
            {
            long m = sc.nextInt();
            long n = sc.nextInt();
            int count = 0;
            for(long j=m;j<=n;j++)
                {
               
               
                boolean b = perfectSquare(j);
                if(b==true){
                        long sqrt = (long) Math.sqrt(j);
                        j=j+sqrt+sqrt;
                    count++;
                }
               
            }
            System.out.println(count);
            count = 0;
           
        }
    }
   
    public static boolean perfectSquare(long number)
        {
       
        long sqrt = (long) Math.sqrt(number);

                if(sqrt*sqrt == number) {

                    return true;

                }else {

                    return false;

                }
    }
}