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 codeint main(){ long N = 3; cout << SmallestPerfectSquare(N); return 0;}// This code is contributed by Utkarsh Kumar. |
Java
// Java code of above approachimport 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 approachimport 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 codeN = 3print(SmallestPerfectSquare(N))# This code is contributed by prasad264 |
C#
// C# code of above approachusing 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 approachfunction 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 mathdef 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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
