Problem Description
Given a number N, find the square root of that number. If the number is not a perfect square, then return -1
Solution
First approach - Brute Force
Brute Force: Loop through all the numbers till N and check if there is any number which when multiplied with itself gives N.
Second approach - Binary Search
Binary Search Approach: Pick up the middle element. Check if it is the required root. If not, check if that number (ixi) is greater than N. If (ixi) is greater than N, it means that we can ignore all the numbers which are right to i.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.test;
public class Solution {
public static void main(String[] args) {
System.out.println(findSquareRootv1(25));
System.out.println(findSquareRootv2(25));
}
//brute force
public static int findSquareRootv1(int n) {
for(int i=1; i<=n; i++) {
if(i*i == n) {
return i;
}
}
return -1;
}
//using binary search approach
public static int findSquareRootv2(int n) {
if(n == 0) return 0;
if(n < 0) return -1;
int[] arr = new int[n];
for(int i=0; i<n;i++) {
arr[i] = i+1;
}
int i=0;
int j=n-1;
int mid=0;
while(i<=j) {
mid = (i+j)/2;
int checkNum = arr[mid] * arr[mid];
if(checkNum == n) {
return arr[mid];
}else if(checkNum < n) {
i = mid+1;
}else {
j = mid-1;
}
}
return -1;
}
}
Better way to code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int mySqrt(int x) {
long l = 0;
long r = x;
long idx = -1;
while(l<=r){
long m = (l+r)/2;
if(m*m == x) return (int) m;
if(m*m > x){
r = m-1;
}else{
idx = m;
l = m+1;
}
}
return (int)idx;
}
}