Given an integer N, the task is to find two non-negative integers A and B, such that A2 – B2 = N. If no such integers exist, then print -1.
Examples:
Input: N = 7
Output: 4 3
Explanation:
The two integers 4 and 3 can be represented as 42 – 32 = 7.
Input: N = 6
Output: -1
Explanation:
No pair of (A, B) exists that satisfies the required condition.
Approach:
- A2 – B2 can be represented as (A – B) * (A + B).
A2 – B2 = (A – B) * (A + B)
- Thus, for A2 – B2 to be equal to N, both (A + B) and (A – B) should be divisors of N.
- Considering A + B and A – B to be equal to C and D respectively, then C and D must be divisors of N such that C ? D and C and D should be of the same parity.
- Hence, in order to solve this problem, we just need to find any pair C and D satisfying the above condition. If no such C & D exists, then the print -1.
Below is the implementation of the above approach:
C++
// C++ Program to find two numbers// with difference of their// squares equal to N#include <bits/stdc++.h>using namespace std;// Function to check and print// the required two positive integersvoid solve(int n){ // Iterate till sqrt(n) to find // factors of N for (int x = 1; x <= sqrt(n); x++) { // Check if x is one // of the factors of N if (n % x == 0) { // Store the factor int small = x; // Compute the other factor int big = n / x; // Check if the two factors // are of the same parity if (small % 2 == big % 2) { // Compute a and b int a = (small + big) / 2; int b = (big - small) / 2; cout << a << " " << b << endl; return; } } } // If no pair exists cout << -1 << endl;}// Driver Codeint main(){ int n = 7; solve(n); return 0;} |
Java
// Java Program to find two numbers// with difference of their// squares equal to Nimport java.util.*;class GFG{// Function to check and print// the required two positive integersstatic void solve(int n){ // Iterate till sqrt(n) to find // factors of N for (int x = 1; x <= Math.sqrt(n); x++) { // Check if x is one // of the factors of N if (n % x == 0) { // Store the factor int small = x; // Compute the other factor int big = n / x; // Check if the two factors // are of the same parity if (small % 2 == big % 2) { // Compute a and b int a = (small + big) / 2; int b = (big - small) / 2; System.out.print(a + " " + b); return; } } } // If no pair exists System.out.print(-1);}// Driver Codepublic static void main(String args[]){ int n = 7; solve(n);}}// This code is contributed by Code_Mech |
Python3
# Python3 Program to find two numbers # with difference of their # squares equal to N from math import sqrt# Function to check and print # the required two positive integers def solve(n) : # Iterate till sqrt(n) to find # factors of N for x in range(1, int(sqrt(n)) + 1) : # Check if x is one # of the factors of N if (n % x == 0) : # Store the factor small = x; # Compute the other factor big = n // x; # Check if the two factors # are of the same parity if (small % 2 == big % 2) : # Compute a and b a = (small + big) // 2; b = (big - small) // 2; print(a, b) ; return; # If no pair exists print(-1); # Driver Codeif __name__ == "__main__" : n = 7; solve(n); # This code is contributed by AnkitRai01 |
C#
// C# Program to find two numbers// with difference of their// squares equal to Nusing System;class GFG{// Function to check and print// the required two positive integersstatic void solve(int n){ // Iterate till sqrt(n) to find // factors of N for (int x = 1; x <= Math.Sqrt(n); x++) { // Check if x is one // of the factors of N if (n % x == 0) { // Store the factor int small = x; // Compute the other factor int big = n / x; // Check if the two factors // are of the same parity if (small % 2 == big % 2) { // Compute a and b int a = (small + big) / 2; int b = (big - small) / 2; Console.WriteLine(a + " " + b); return; } } } // If no pair exists Console.WriteLine(-1);}// Driver Codepublic static void Main(){ int n = 7; solve(n);}}// This code is contributed by Code_Mech |
Javascript
<script>// javascript Program to find two numbers// with difference of their// squares equal to N // Function to check and print // the required two positive integers function solve(n) { // Iterate till sqrt(n) to find // factors of N for (var x = 1; x <= Math.sqrt(n); x++) { // Check if x is one // of the factors of N if (n % x == 0) { // Store the factor var small = x; // Compute the other factor var big = n / x; // Check if the two factors // are of the same parity if (small % 2 == big % 2) { // Compute a and b var a = (small + big) / 2; var b = (big - small) / 2; document.write(a + " " + b); return; } } } // If no pair exists document.write(-1); } // Driver Code var n = 7; solve(n);// This code contributed by aashish1995</script> |
Output
4 3
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Approach#2: Using brute force
This approach is to use two nested loops to generate all possible pairs of integers (i, j) such that i < j. We then check if the difference of their squares is equal to N. If we find a pair that satisfies this condition, we return the pair. If no such pair exists, we return -1.
Algorithm
1. Initialize a nested loop that iterates over all possible pairs of integers (i, j) such that i < j.
2. Compute the difference of their squares, (j^2 – i^2).
3. If (j^2 – i^2) is equal to N, return the pair (j, i) as a string.
4. If no pair is found that satisfies the condition, return -1.
Java
// Java code of the above approachpublic class GFG { public static String findNumbersWithSquareDifference(int N) { for (int i = 1; i < N; i++) { for (int j = i + 1; j <= N; j++) { if (j * j - i * i == N) { return j + " " + i; } } } return "-1"; } public static void main(String[] args) { int N = 7; System.out.println( findNumbersWithSquareDifference(N)); }} |
Python3
def find_numbers_with_square_difference(N): for i in range(1, N): for j in range(i+1, N+1): if j**2 - i**2 == N: return f"{j} {i}" return "-1"N=7print(find_numbers_with_square_difference(N)) |
Output
4 3
Time Complexity: O(N^2) because we use two nested loops to iterate over all possible pairs of integers from 1 to N.
Space Complexity: O(1) because we only store the variables i, j, and the return string, which do not depend on the input size N.
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!
