Square Root Editorial

Problem Statement

Given a non-negative integer ‘n’, compute and return the square root of ‘n’. If n is not a perfect square, return the floor of the result.

Naive Approach

We can check for all numbers from 1 to n such that if the square of the number is just greater than or equal to n.

• Run a loop from i=1 to i=n.
• Check if i*i greater than n.
• As soon as the above condition is met return the value of i-1 and break the loop.

Analysis

• Time Complexity:O(sqrt(n))
• Space Complexity: O(1)

Implementation

C++

int searchRoot(int num) {
   if (num == 0 || num == 1) {
       return num;
   }
   for (int i = 1; i < num; i++) {
       if(i * i > num){
           return i - 1;
       }
   }
}

Java

class Solution {
   int searchRoot (int num) {
       if (num == 0 || num == 1) {
           return num;
       }
       for (int i = 1; i < num; i++) {
           if( i * i > num ) {
               return i - 1;
           }
       }
       return 0;
   }
}

Optimal Approach

The problem can be solved by using the concept of binary search from 1 to n to find a value whose square is equal to or just less than n.

• Declare four variables low=1(lower bound) and high=n(upper bound), mid and ans to store the answer.
• Initialize ans=1 as the base condition.
• Run a loop until (low<=high).
• Initialize mid=(low+high)/2 and check if the square of mid is less than or equal to n. If yes, assign ans=mid and search for a larger value in the range mid+1 to high otherwise initialize high=mid-1 and search for a smaller value in the range low to mid-1.
• Return the value of ans at last.
• Take care of case (n=0 and n=1) separately.

Analysis

• Time Complexity:O(log(n))
• Space Complexity:O(1)

Implementation

C++ (Iterative)

int searchRoot(int num) {
   if (num == 0 || num == 1) {
       return num;
   }
   int low = 1, high = num, mid, ans = 1;
   while (low <= high) {
       mid = (high + low) / 2;
       if (mid <= num / mid) {
           low = mid + 1;
           ans = mid;
       } else {
           high = mid - 1;
       }
   }
   return ans;
}

C++ (Recursive)

int ans;
int binarySearch (int low, int high, int num) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if (mid <= num / mid) {
           ans = mid;
           return binarySearch (mid + 1, high, num);
     } else {
           return binarySearch (low, mid - 1, num);
       }
   }
   return ans;
}
int searchRoot(int num) {
   if (num == 0 || num == 1) {
       return num;
   }
   ans = binarySearch (1, num, num);
   return ans;
}

Java (Iterative)

class Solution {
  int searchRoot (int num) {
      if (num == 0 || num == 1) {
          return num;
      }
      int low = 1, high = num, mid, ans = 1;
      while (low <= high) {
          mid = (high + low) / 2;
          if (mid <= num / mid) {
              ans = mid;
              low = mid + 1;
          } else {
              high = mid - 1;
          }
      }
      return ans;
  }
}

Java (Recursive)

class Solution {
   int ans;
   int binarySearch (int low, int high, int num) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if (mid <= num / mid) {
               ans = mid;
               return binarySearch (mid + 1, high, num);
           } else {
               return binarySearch (low, mid - 1, num);
           }
       }
       return ans;
   }
   int searchRoot (int num) {
       if (num == 0 || num == 1) {
           return num;
       }
       ans = binarySearch (1, num, num);
       return ans;
   }
}