Given sum and gcd of two numbers 
and 
. The task is to find both the numbers a and b. If the numbers do not exist then print 
.
Examples:
Input: sum = 6, gcd = 2
Output: a = 4, b = 2
4 + 2 = 6 and GCD(4, 2) = 2
Input: sum = 7, gcd = 2
Output: -1
There are no such numbers whose sum is 7 and GCD is 2
Approach: As GCD is given then it is known that both the numbers will be multiples of it.
- Choose the first number as gcd then the other number will be sum – gcd.
- If the sum of both the numbers chosen in the previous step equals to sum then print both the numbers.
- Else the numbers do not exist and print -1 instead.
Below is the implementation of the above approach:
C++
// C++ program to find two numbers// whose sum and GCD is given#include <bits/stdc++.h>using namespace std;// Function to find two numbers// whose sum and gcd is givenvoid findTwoNumbers(int sum, int gcd){ // sum != gcd checks that both the // numbers are positive or not if (__gcd(gcd, sum - gcd) == gcd && sum != gcd) cout << "a = " << min(gcd, sum - gcd) << ", b = " << sum - min(gcd, sum - gcd) << endl; else cout << -1 << endl;}// Driver codeint main(){ int sum = 8; int gcd = 2; findTwoNumbers(sum, gcd); return 0;} |
Java
// Java program to find two numbers // whose sum and GCD is given import java.util.*;class Solution{//function to find gcd of two numbersstatic int __gcd(int a,int b){ if (b==0) return a; return __gcd(b,a%b);} // Function to find two numbers // whose sum and gcd is given static void findTwoNumbers(int sum, int gcd) { // sum != gcd checks that both the // numbers are positive or not if (__gcd(gcd, sum - gcd) == gcd && sum != gcd) System.out.println( "a = " + Math.min(gcd, sum - gcd) + ", b = " + (int)(sum - Math.min(gcd, sum - gcd)) ); else System.out.println( -1 ); } // Driver code public static void main(String args[]) { int sum = 8; int gcd = 2; findTwoNumbers(sum, gcd); } }//contributed by Arnab Kundu |
Python3
# Python 3 program to find two numbers# whose sum and GCD is givenfrom math import gcd as __gcd# Function to find two numbers# whose sum and gcd is givendef findTwoNumbers(sum, gcd): # sum != gcd checks that both the # numbers are positive or not if (__gcd(gcd, sum - gcd) == gcd and sum != gcd): print("a =", min(gcd, sum - gcd), ", b =", sum - min(gcd, sum - gcd)) else: print(-1) # Driver codeif __name__ == '__main__': sum = 8 gcd = 2 findTwoNumbers(sum, gcd)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find two numbers // whose sum and GCD is given using System;class GFG{// function to find gcd of two numbersstatic int __gcd(int a, int b){ if (b == 0) return a; return __gcd(b, a % b);} // Function to find two numbers // whose sum and gcd is given static void findTwoNumbers(int sum, int gcd) { // sum != gcd checks that both the // numbers are positive or not if (__gcd(gcd, sum - gcd) == gcd && sum != gcd) Console.WriteLine("a = " + Math.Min(gcd, sum - gcd) + ", b = " + (int)(sum - Math.Min(gcd, sum - gcd))); else Console.WriteLine( -1 ); } // Driver code public static void Main() { int sum = 8; int gcd = 2; findTwoNumbers(sum, gcd); } }// This code is contributed by anuj_67.. |
PHP
<?php// PHP program to find two numbers // whose sum and GCD is given // Function to find gcd of two numbers function __gcd($a, $b) { if ($b == 0) return $a; return __gcd($b, $a % $b); } // Function to find two numbers // whose sum and gcd is given function findTwoNumbers($sum, $gcd) { // sum != gcd checks that both the // numbers are positive or not if (__gcd($gcd, $sum - $gcd) == $gcd && $sum != $gcd) echo "a = " , min($gcd, $sum - $gcd), " b = ", (int)($sum - min($gcd, $sum - $gcd)); else echo (-1); } // Driver code $sum = 8; $gcd = 2; findTwoNumbers($sum, $gcd); // This code is contributed by Sachin?> |
Javascript
<script>// Javascript program to find two numbers // whose sum and GCD is given //function to find gcd of two numbersfunction __gcd(a, b){ if (b==0) return a; return __gcd(b,a%b);} // Function to find two numbers // whose sum and gcd is given function findTwoNumbers(sum, gcd) { // sum != gcd checks that both the // numbers are positive or not if (__gcd(gcd, sum - gcd) == gcd && sum != gcd) document.write( "a = " + Math.min(gcd, sum - gcd) + ", b = " + (sum - Math.min(gcd, sum - gcd)) ); else document.write( -1 ); } // Driver code let sum = 8; let gcd = 2; findTwoNumbers(sum, gcd); </script> |
Output:
a = 2, b = 6
Time Complexity: O(log(min(a, b))), where a and b are two parameters of gcd.
Auxiliary Space: O(log(min(a, b)))
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!
