Count of all possible pairs having sum of LCM and GCD equal to N

0 0 4 minutes read

Given an integer N, the task is to find the count of all possible pairs of integers (A, B) such that GCD (A, B) + LCM (A, B) = N.

Examples:

Input: N = 14
Output: 7
Explanation:
All the possible pairs are {1, 13}, {2, 12}, {4, 6}, {6, 4}, {7, 7}, {12, 2}, {13, 1}

Input: N = 6
Output: 5

Approach:
Follow the steps below to solve the problem:

Initialize a variable count, to store the count of all the possible pairs.
Iterate over the range [1, N] to generate all possible pairs (i, j). Calculate the GCD of (i, j) using the __gcd() function and calculate LCM of (i, j).
Now, check if the sum of LCM (i, j) and GCD (i, j) is equal to N or not. If so, increment count.
Print the count value after the complete traversal of the range.

Below is the implementation of the above approach:

C++

// C++ Program to implement 
// the above approach 
#include <bits/stdc++.h> 
using namespace std; 
 
// Function to calculate and 
// return LCM of two numbers 
int lcm(int a, int b) 
{ 
    return (a * b) / __gcd(a, b); 
} 
 
// Function to count pairs 
// whose sum of GCD and LCM 
// is equal to N 
int countPair(int N) 
{ 
    int count = 0; 
    for (int i = 1; 
        i <= N; i++) { 
 
        for (int j = 1; 
            j <= N; j++) { 
 
            if (__gcd(i, j) 
                    + lcm(i, j) 
                == N) { 
 
                count++; 
            } 
        } 
    } 
 
    return count; 
} 
 
// Driver Code 
int main() 
{ 
    int N = 14; 
    cout << countPair(N); 
 
    return 0; 
} 

Java

// Java program to implement 
// the above approach 
class GFG{ 
 
// Recursive function to return gcd of a and b 
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b); 
} 
 
// Function to calculate and 
// return LCM of two numbers 
static int lcm(int a, int b) 
{ 
    return (a * b) / __gcd(a, b); 
} 
 
// Function to count pairs 
// whose sum of GCD and LCM 
// is equal to N 
static int countPair(int N) 
{ 
    int count = 0; 
    for(int i = 1; i <= N; i++) 
    { 
        for(int j = 1; j <= N; j++) 
        { 
            if (__gcd(i, j) + lcm(i, j) == N) 
            { 
                count++; 
            } 
        } 
    } 
    return count; 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
    int N = 14; 
     
    System.out.print(countPair(N)); 
} 
} 
 
// This code is contributed by Rajput-Ji 

Python3

# Python3 program to implement  
# the above approach  
 
# Recursive function to return 
# gcd of a and b  
def __gcd(a, b):  
     
    if b == 0:
        return a
    else:
        return __gcd(b, a % b)
     
# Function to calculate and  
# return LCM of two numbers  
def lcm(a, b):
 
    return (a * b) // __gcd(a, b)  
 
# Function to count pairs  
# whose sum of GCD and LCM  
# is equal to N  
def countPair(N):  
 
    count = 0
     
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if (__gcd(i, j) + lcm(i, j) == N):  
                count += 1 
             
    return count 
 
# Driver code
if __name__=="__main__":
     
    N = 14 
       
    print(countPair(N))
 
# This code is contributed by rutvik_56

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);
}
 
// Function to calculate and
// return LCM of two numbers
static int lcm(int a, int b)
{
    return (a * b) / __gcd(a, b);
}
 
// Function to count pairs
// whose sum of GCD and LCM
// is equal to N
static int countPair(int N)
{
    int count = 0;
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if (__gcd(i, j) + lcm(i, j) == N)
            {
                count++;
            }
        }
    }
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 14;
 
    Console.Write(countPair(N));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// javascript program to implement 
// the above approach     
// Recursive function to return gcd of a and b
    function __gcd(a , b)
    {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Function to calculate and
    // return LCM of two numbers
    function lcm(a , b) {
        return (a * b) / __gcd(a, b);
    }
 
    // Function to count pairs
    // whose sum of GCD and LCM
    // is equal to N
    function countPair(N)
    {
        var count = 0;
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (__gcd(i, j) + lcm(i, j) == N) {
                    count++;
                }
            }
        }
        return count;
    }
 
    // Driver Code
        var N = 14;
        document.write(countPair(N));
 
// This code is contributed by aashish1995
</script>

Output:

Time Complexity: O(N²*log(N)) (here two nested for loops so O(n²) and in between them there is __gcd(a,b) which will run in log(N) time so effective time complexity will be O(N²*log(N)) )
Auxiliary Space: O(logn)

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!