Find two Integers whose GCD is A, and the Difference Between their Squares is B

GAZAL ARORA
Last Updated: May 13, 2022

Prerequisite: GCD

Problem

Given two positive integers, A and B. Find two integers X, Y whose Greatest Common Divisor is A, and the difference between their squares is B. Print "-1" if no such pair exists. You can print any one pair if multiple pairs are possible.

Input: Two positive integers A and B.

Output: Print X and Y if the pair exists or print "-1". Print the larger integer first.

For example,

1.
Input: A = 4, B = 80
Output: 12 8
Explanation: GCD of 12 and 8 is 4, and the difference between their squares is 80. i.e., 144 - 64 = 80.

2.
Input: A = 1, B = 24
Output: 7 5
Explanation: GCD of 7 and 5 is 1, and the difference between their squares is 24. i.e., 49 - 25 = 24.

3.
Input: A = 4, B = 20
Output: -1
Explanation: No such pair exists.

 

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 


Recommended: Please try to solve it yourself before moving on to the solution.

Solution

  1. Let the final two integers be x and y.
  2. According to the problem, x2 - y2 = B and x2 - y2 = (x-y)*(x+y). Therefore, (x+y)*(x-y) = B.
  3. Now x, y, and B are integers, therefore (x+y), (x-y) must be an integer, and (x+y) and (x-y) must be divisors of B.
  4. Let x+y = P and x-y = Q. 
  5. Therefore, x = (P+Q)/2 and y = (P-Q)/2. 
  6. For x and y to be integers, the parity of P and Q must be the same.
  7. Since there are four possible pairs of x and y as (+x, +y), (-x, -y), (+x, -y), and (-x, +y). Therefore, the number of possible solutions is 4*(count pairs of divisors with even sum).
  8. Now we have to find any of those 4 pairs whose gcd is A.

 

C++

#include <bits/stdc++.h>
using namespace std;

// Function to find the pairs x and y with given gcd A and difference between their squares B.
void findPairs(int A, int B)
{
    // Iterate over the divisors of B to find x and y.
    for (int i = 1; i * i <= B; i++) {

    // check if i is a factor of B.
        if (B % i == 0) {
    
            // P = (x+y), first divisor of B.
            // Q = (x-y), second divisor of B.
            int P = i;
            int Q = B / i;

              // As P and Q are integers, their parity must be the same.
            if (P % 2 != Q % 2) {
                continue;
            }

            // x = (P+Q)/2.
            // y = (P-Q)/2.
            int x = (P + Q) / 2;
            int y = (Q - P) / 2;

            // if gcd of x, y is A, the pair (x,y) is valid.
            if (__gcd(x, y) == A) {
                cout << x << " " << y;
                return;
            }
        }
    }
    // Print -1 is no such pair exists.
    cout << -1;
    return;
}

int main()
{
    int A = 4, B = 80;
    findPairs(A, B);
    return 0;
}

Input: A = 4, B = 80

Output: 

12 8

Time Complexity: O(√ B), where B is the given difference between squares of X and Y.

Space Complexity: O(1). 

FAQs

  1. What do you mean by gcd of two integers?
    GCD, or the greatest common divisor of that two integers, is the largest integer, a divisor of each of two or more integers or polynomials. For example, let the given two integers be 10 and 15. Divisors of 10 are 1, 2, 5, 10, and 15 are 1, 3, 5, 15. Their largest common divisor is 5. Hence, gcd of 10 and 15 is 5.
     
  2. What do you mean by the difference of the two squares?
    The difference of two squares in mathematics is a squared (multiplied by itself) number subtracted from another squared number. Every difference in squares can be factored, using the identity:
    a2 + b2 = (a+b) (a-b)

Key takeaways

In this article, we designed an algorithm to find two integers X, Y whose GCD is a given number A, and the difference between their squares is B.
We first found the mathematical relation between X, Y, and the divisors of B and then checked the validity of the pairs calculated using the gcd condition.
The algorithm's time complexity is O(√ B), whereas space complexity is O(1).

Don't stop here. Explore more!

Use CodeStudio to practice various DSA questions asked in different interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.
Happy Coding!

Was this article helpful ?
1 upvote