Given a number N, find the minimum number that needs to be added to or subtracted from N, to make it a perfect square. If the number is to be added, print it with a + sign, else if the number is to be subtracted, print it with a – sign.
Examples:
Input: N = 14
Output: 2
Nearest perfect square before 14 = 9
Nearest perfect square after 14 = 16
Therefore, 2 needs to be added to 14 to get the closest perfect square.Input: N = 18
Output: -2
Nearest perfect square before 18 = 16
Nearest perfect square after 18 = 25
Therefore, 2 needs to be subtracted from 18 to get the closest perfect square.
Approach:
- Get the number.
- Find the square root of the number and convert the result as an integer.
- After converting the double value to an integer, it will contain the root of the perfect square above N, i.e. floor(square root(N)).
- Then find the square of this number, which will be the perfect square before N.
- Find the root of the perfect square after N, i.e. the ceil(square root(N)).
- Then find the square of this number, which will be the perfect square after N.
- Check whether the square of floor value is nearest to N or the ceil value.
- If the square of floor value is nearest to N, print the difference with a -sign. Else print the difference between the square of the ceil value and N with a + sign.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the Least number int nearest( int n) { // Get the perfect square // before and after N int prevSquare = sqrt (n); int nextSquare = prevSquare + 1; prevSquare = prevSquare * prevSquare; nextSquare = nextSquare * nextSquare; // Check which is nearest to N int ans = (n - prevSquare) < (nextSquare - n) ? (prevSquare - n) : (nextSquare - n); // return the result return ans; } // Driver code int main() { int n = 14; cout << nearest(n) << endl; n = 16; cout << nearest(n) << endl; n = 18; cout << nearest(n) << endl; return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the Least number static int nearest( int n) { // Get the perfect square // before and after N int prevSquare = ( int )Math.sqrt(n); int nextSquare = prevSquare + 1 ; prevSquare = prevSquare * prevSquare; nextSquare = nextSquare * nextSquare; // Check which is nearest to N int ans = (n - prevSquare) < (nextSquare - n)? (prevSquare - n): (nextSquare - n); // return the result return ans; } // Driver code public static void main (String[] args) { int n = 14 ; System.out.println(nearest(n)); n = 16 ; System.out.println(nearest(n)) ; n = 18 ; System.out.println(nearest(n)) ; } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach from math import sqrt # Function to return the Least number def nearest(n) : # Get the perfect square # before and after N prevSquare = int (sqrt(n)); nextSquare = prevSquare + 1 ; prevSquare = prevSquare * prevSquare; nextSquare = nextSquare * nextSquare; # Check which is nearest to N ans = (prevSquare - n) if (n - prevSquare) < (nextSquare - n) else (nextSquare - n); # return the result return ans; # Driver code if __name__ = = "__main__" : n = 14 ; print (nearest(n)) ; n = 16 ; print (nearest(n)); n = 18 ; print (nearest(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the Least number static int nearest( int n) { // Get the perfect square // before and after N int prevSquare = ( int )Math.Sqrt(n); int nextSquare = prevSquare + 1; prevSquare = prevSquare * prevSquare; nextSquare = nextSquare * nextSquare; // Check which is nearest to N int ans = (n - prevSquare) < (nextSquare - n)? (prevSquare - n): (nextSquare - n); // return the result return ans; } // Driver code public static void Main ( string [] args) { int n = 14; Console.WriteLine(nearest(n)); n = 16; Console.WriteLine(nearest(n)) ; n = 18; Console.WriteLine(nearest(n)) ; } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the above approach // Function to return the Least number function nearest( n) { // Get the perfect square // before and after N var prevSquare = parseInt(Math.sqrt(n)); var nextSquare = prevSquare + 1; prevSquare = prevSquare * prevSquare; nextSquare = nextSquare * nextSquare; // Check which is nearest to N if ((n - prevSquare) < (nextSquare - n)) { ans = parseInt((prevSquare - n)); } else ans = parseInt((nextSquare - n)); // return the result return ans; } var n = 14; document.write( nearest(n) + "<br>" ); n = 16; document.write( nearest(n) + "<br>" ); n = 18; document.write( nearest(n) + "<br>" ); // This code is contributed by SoumikMondal </script> |
2 0 -2
Time Complexity: O(logn) as it is using inbuilt sqrt function
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!