Given an integer N, the task is to find its perfect square root by repeated subtraction only.
Examples:
Input: N = 25
Output: 5
Input: N = 841
Output: 29
Babylonian Method and Binary Search Approach: Refer to Square root of an integer for the approaches based on Babylonian Method and Binary Search.
Repeated Subtraction Approach:
Follow the steps below to solve the problem:
- Sum of the first N odd natural numbers is equal to N2.
- Based on the fact mentioned above, repetitive subtraction of odd numbers starting from 1, until N becomes 0 needs to be performed.
- The count of odd numbers, used in this process, will give the square root of the number N.
Illustration:
N = 81
Step 1: 81-1=80
Step 2: 80-3=77
Step 3: 77-5=72
Step 4: 72-7=65
Step 5: 65-9=56
Step 6: 56-11=45
Step 7: 45-13=32
Step 8: 32-15=17
Step 9: 17-17=0
Since, 9 odd numbers were used, hence the square root of 81 is 9.
Below is the implementation of the above approach.
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; // Function to return the square // root of the given number int SquareRoot( int num) { int count = 0; for ( int n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break ; } // Return the result return count; } // Driver Code int main() { int N = 81; cout << SquareRoot(N); } |
Java
// Java implementation of // the above approach class GFG{ // Function to return the square // root of the given number public static int SquareRoot( int num) { int count = 0 ; for ( int n = 1 ; n <= num; n += 2 ) { // Subtract n-th odd number num = num - n; count += 1 ; if (num == 0 ) break ; } // Return the result return count; } // Driver code public static void main(String[] args) { int N = 81 ; System.out.println(SquareRoot(N)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation of the # above approach # Function to return the square # root of the given number def SquareRoot(num): count = 0 for n in range ( 1 , num + 1 , 2 ): # Subtract n-th odd number num = num - n count = count + 1 if (num = = 0 ): break # Return the result return count # Driver Code N = 81 print (SquareRoot(N)) # This code is contributed by Sanjit_Prasad |
C#
// C# implementation of // the above approach using System; class GFG{ // Function to return the square // root of the given number public static int SquareRoot( int num) { int count = 0; for ( int n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break ; } // Return the result return count; } // Driver code public static void Main() { int N = 81; Console.Write(SquareRoot(N)); } } // This code is contributed by chitranayal |
Javascript
<script> // Javascript implementation of // the above approach // Function to return the square // root of the given number function SquareRoot(num) { let count = 0; for (let n = 1; n <= num; n += 2) { // Subtract n-th odd number num = num - n; count += 1; if (num == 0) break ; } // Return the result return count; } // Driver Code let N = 81; document.write(SquareRoot(N)); // This code is contributed by Mayank Tyagi </script> |
9
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!