Find smallest perfect square number A such that N + A is also a perfect square number

0 0 7 minutes read

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 = 2²

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

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:

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 zambiatek!