Number of perfect squares between two given numbers - GeeksforGeeks
Given two given numbers a and b where 1<=a<=b, find the number of perfect squares between a and b (a and b inclusive).
Time complexity of this solution is O(Log b). A typical implementation of square root for a number n takes time equal to O(Log n)
http://www.geeksforgeeks.org/square-root-of-an-integer/
A Simple Solution to find floor of square root is to try all numbers starting from 1. For every tried number i, if i*i is smaller than x, then increment i. We stop when i*i becomes more than or equal to x.
Read full article from Number of perfect squares between two given numbers - GeeksforGeeks
Given two given numbers a and b where 1<=a<=b, find the number of perfect squares between a and b (a and b inclusive).
Input : a = 9, b = 25 Output : 3 The three squares in given range are 9, 16 and 25
Method 2 (Efficient) We can simply take square root of ‘a’ and square root of ‘b’ and count the perfect squares between them using
floor(sqrt(b)) - ceil(sqrt(a)) + 1 We take floor of sqrt(b) because we need to consider numbers before b. We take ceil of sqrt(a) because we need to consider numbers after a. For example, let b = 24, a = 8. floor(sqrt(b)) = 4, ceil(sqrt(a)) = 3. And number of squares is 4 - 3 + 1 = 2. The two numbers are 9 and 16.
double countSquares(int a,int b) { return (Math.floor(Math.sqrt(b)) - Math.ceil(Math.sqrt(a)) + 1); }Time complexity of this solution is O(Log b). A typical implementation of square root for a number n takes time equal to O(Log n)
static int countSquares(int a, int b) { int cnt = 0; // Initialize result // Traverse through all numbers for (int i=a; i<=b; i++) // Check if current number 'i' is perfect // square for (int j=1; j*j<=i; j++) if (j*j==i) cnt++; return cnt; }
A Better Solution to do Binary Search.
Let 's' be the answer. We know that 0 <= s <= x.
Consider any random number r.
If r*r <= x, s >= r
If r*r > x, s < r.
Algorithm:
1) Start with 'start' = 0, end = 'x',
2) Do following while 'start' is smaller than or equal to 'end'.
a) Compute 'mid' as (start + end)/2
b) compare mid*mid with x.
c) If x is equal to mid*mid, return mid.
d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor).
e) If x is smaller, do binary search between start and mid-1
1) Start with 'start' = 0, end = 'x',
2) Do following while 'start' is smaller than or equal to 'end'.
a) Compute 'mid' as (start + end)/2
b) compare mid*mid with x.
c) If x is equal to mid*mid, return mid.
d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor).
e) If x is smaller, do binary search between start and mid-1
Time Complexity: O(Log x)
Note: The Binary Search can be further optimized to start with 'start' = 0 and 'end' = x/2. Floor of square root of x cannot be more than x/2 when x > 1.
public static int floorSqrt(int x) { // Base Cases if (x == 0 || x == 1) return x; // Do Binary Search for floor(sqrt(x)) int start = 1, end = x, ans=0; while (start <= end) { int mid = (start + end) / 2; // If x is a perfect square if (mid*mid == x) return mid; // Since we need floor, we update answer when mid*mid is // smaller than x, and move closer to sqrt(x) if (mid*mid < x) { start = mid + 1; ans = mid; } else // If mid*mid is greater than x end = mid - 1; } return ans; }A Simple Solution to find floor of square root is to try all numbers starting from 1. For every tried number i, if i*i is smaller than x, then increment i. We stop when i*i becomes more than or equal to x.
int floorSqrt(int x){ // Base cases if (x == 0 || x == 1) return x; // Staring from 1, try all numbers until // i*i is greater than or equal to x. int i = 1, result = 1; while (result < x) { if (result == x) return result; i++; result = i*i; } return i-1;}