Find smallest perfect square number A such that N + A is also a perfect square number
Given a positive number N. The task is to find out the smallest perfect square number A such that N + A is also a perfect square number or return -1.
Examples:
Input: N = 3 Output: 1 Explanation: As 1 + 3 = 4 = 22 Input: N=1 Output: -1
Naive Approach:
Traverse M from {1, 2, 3, 4, 5…} and check whether (N + M * M) is a perfect square number or not.
C++
// C++ code of above approach #include<bits/stdc++.h> using namespace std; // Check if number is perfect square // or not. bool checkperfectsquare( int n) { // If ceil and floor are equal // the number is a perfect // square if ( ceil (( double ) sqrt (n)) == floor (( double ) sqrt (n))) { return true ; } else { return false ; } } // Function to find out the smallest // perfect square X which when added to N // yields another perfect square number. long SmallestPerfectSquare( long N){ long X = ( long )1e9; long ans=-1; for ( int i=1;i<=X;i++) { if (checkperfectsquare(N+i*i)) { ans=i*i; break ; } } return ans; } // Driver code int main() { long N = 3; cout << SmallestPerfectSquare(N); return 0; } // This code is contributed by Utkarsh Kumar. |
Java
// Java code of above approach import java.util.*; class GFG { // Check if number is perfect square // or not. public static boolean checkperfectsquare( long n) { // If ceil and floor are equal // the number is a perfect // square if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) { return true ; } else { return false ; } } // Function to find out the smallest // perfect square X which when added to N // yields another perfect square number. public static long SmallestPerfectSquare( long N) { long X = ( long )1e9; long ans = - 1 ; for ( int i = 1 ; i <= X; i++) { if (checkperfectsquare(N + ( long )i * i)) { ans = i * i; break ; } } return ans; } // Driver code public static void main(String[] args) { long N = 3 ; System.out.println(SmallestPerfectSquare(N)); } } // This code is contributed by prasad264 |
Python3
# Python code of above approach import math # Check if number is perfect square # or not. def checkperfectsquare(n): # If ceil and floor are equal # the number is a perfect # square if math.ceil(math.sqrt(n)) = = math.floor(math.sqrt(n)): return True else : return False # Function to find out the smallest # perfect square X which when added to N # yields another perfect square number. def SmallestPerfectSquare(N): X = int ( 1e9 ) ans = - 1 for i in range ( 1 , X + 1 ): if checkperfectsquare(N + i * i): ans = i * i break return ans # Driver code N = 3 print (SmallestPerfectSquare(N)) # This code is contributed by prasad264 |
C#
// C# code of above approach using System; class Program { // Check if number is perfect square or not. static bool CheckPerfectSquare( long n) { // If ceil and floor are equal the number is a perfect square. if (Math.Ceiling(Math.Sqrt(n)) == Math.Floor(Math.Sqrt(n))) { return true ; } else { return false ; } } // Function to find out the smallest perfect square X // which when added to N yields another perfect square number. static long SmallestPerfectSquare( long N) { long X = ( long )1e9; long ans = -1; for ( int i = 1; i <= X; i++) { if (CheckPerfectSquare(N + i * i)) { ans = i * i; break ; } } return ans; } // Driver code static void Main() { long N = 3; Console.WriteLine(SmallestPerfectSquare(N)); } } |
Javascript
// Javascript code of above approach function checkperfectsquare(n) { // If ceil and floor are equal // the number is a perfect // square if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) { return true ; } else { return false ; } } function SmallestPerfectSquare(N) { const X = 1000000000; let ans = -1; for (let i = 1; i <= X; i++) { if (checkperfectsquare(N + i * i)) { ans = i * i; break ; } } return ans; } const N = 3; console.log(SmallestPerfectSquare(N)); |
Output
1
Time complexity: O(X*log(X)) where X=1e9 here
Auxiliary Space: O(1)
Efficient Approach:
- On observing, we have an equation like:
- N + (X * X) = (M * M) where N is given and M and X are unknown.
- We can rearrange it and get:
- N = (M * M) – (X * X)
- N = (M + X) * (M – X)
- Now we can see that for obtaining N, we need to find the factor of N.The factor of N can be obtained in O(N) time. But it can be optimized to O(N^1/2) by this method.
- Let the factor of N be a and b = (N / a). So, from the above equation a = (M – X) and b = (M + X), and after solving this we can obtain the value of X = (b – a)/2.
Below is the implementation of the above approach:
C++
// C++ code to find out the smallest // perfect square X which when added to N // yields another perfect square number. #include<bits/stdc++.h> using namespace std; long SmallestPerfectSquare( long N){ // X is the smallest perfect // square number long X = ( long )1e9; long ans; // Loop from 1 to square root of N for ( int i = 1; i < sqrt (N); i++) { // Condition to check whether i // is factor of N or not if (N % i == 0) { long a = i; long b = N / i; // Condition to check whether // factors satisfies the // equation or not if ((b - a != 0) && ((b - a) % 2 == 0)) { // Stores minimum value X = min(X, (b - a) / 2); } } } // Return if X * X if X is not equal // to 1e9 else return -1 if (X != 1e9) ans = X * X; else ans = -1; return ans; } // Driver code int main() { long N = 3; cout << SmallestPerfectSquare(N); return 0; } // This code is contributed by AnkitRai01 |
Java
// Java code to find out the smallest // perfect square X which when added to N // yields another perfect square number. public class GFG { static long SmallestPerfectSquare( long N) { // X is the smallest perfect // square number long X = ( long )1e9; long ans; // Loop from 1 to square root of N for ( int i = 1 ; i < Math.sqrt(N); i++){ // Condition to check whether i // is factor of N or not if (N % i == 0 ){ long a = i ; long b = N / i; // Condition to check whether // factors satisfies the // equation or not if ((b - a != 0 ) && ((b - a) % 2 == 0 )){ // Stores minimum value X = Math.min(X, (b - a) / 2 ) ; } } } // Return if X * X if X is not equal // to 1e9 else return -1 if (X != 1e9) ans = X * X; else ans = - 1 ; return ans; } // Driver code public static void main (String[] args){ long N = 3 ; System.out.println(SmallestPerfectSquare(N)) ; } } // This code is contributed by AnkitRai01 |
Python3
# Python3 code to find out the smallest # perfect square X which when added to N # yields another perfect square number. import math def SmallestPerfectSquare(N): # X is the smallest perfect # square number X = 1e9 # Loop from 1 to square root of N for i in range ( 1 , int (math.sqrt(N)) + 1 ): # Condition to check whether i # is factor of N or not if N % i = = 0 : a = i b = N / / i # Condition to check whether # factors satisfies the # equation or not if b - a ! = 0 and (b - a) % 2 = = 0 : # Stores minimum value X = min (X, (b - a) / / 2 ) # Return if X * X if X is not equal # to 1e9 else return -1 return (X * X if X ! = 1e9 else - 1 ) # Driver code if __name__ = = "__main__" : N = 3 print (SmallestPerfectSquare(N)) |
C#
// C# code to find out the smallest // perfect square X which when added to N // yields another perfect square number. using System; class GFG { static long SmallestPerfectSquare( long N) { // X is the smallest perfect // square number long X = ( long )1e9; long ans; // Loop from 1 to square root of N for ( int i = 1; i < Math.Sqrt(N); i++){ // Condition to check whether i // is factor of N or not if (N % i == 0) { long a = i; long b = N / i; // Condition to check whether // factors satisfies the // equation or not if ((b - a != 0) && ((b - a) % 2 == 0)) { // Stores minimum value X = Math.Min(X, (b - a) / 2); } } } // Return if X*X if X is not equal // to 1e9 else return -1 if (X != 1e9) ans = X * X; else ans = -1; return ans; } // Driver code public static void Main ( string [] args) { long N = 3; Console.WriteLine(SmallestPerfectSquare(N)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript code to find out the smallest // perfect square X which when added to N // yields another perfect square number. function SmallestPerfectSquare(N){ // X is the smallest perfect // square number let X = 1e9; let ans; // Loop from 1 to square root of N for (let i = 1; i < Math.sqrt(N); i++) { // Condition to check whether i // is factor of N or not if (N % i == 0) { let a = i; let b = N / i; // Condition to check whether // factors satisfies the // equation or not if ((b - a != 0) && ((b - a) % 2 == 0)) { // Stores minimum value X = Math.min(X, (b - a) / 2); } } } // Return if X * X if X is not equal // to 1e9 else return -1 if (X != 1e9) ans = X * X; else ans = -1; return ans; } // Driver code let N = 3; document.write(SmallestPerfectSquare(N)); // This code is contributed by Surbhi Tyagi. </script> |
Output:
1
Time complexity: O(sqrt(N)), since the loop runs from 0 to the square root of N the algorithm takes Sqrt(N) time to run efficiently
Auxiliary Space: O(1), since no extra array is used it takes up constant extra space