Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
2.
Solution
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024

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

Author GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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). 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

You can also consider our Competitive Programming Course to give your career an edge over others!
Happy Coding!

Previous article
Average Value of Set Bit Count in Given Binary String after Performing All Possible Choices of M Operations
Next article
Cycle and cord
Live masterclass