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 codeif __name__=="__main__": N = 14 print(countPair(N))# This code is contributed by rutvik_56 |
C#
// C# program to implement// the above approachusing System;class GFG{// Recursive function to return gcd of a and bstatic int __gcd(int a, int b){ return b == 0 ? a : __gcd(b, a % b);}// Function to calculate and// return LCM of two numbersstatic 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 Nstatic 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 Codepublic 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:
7
Time Complexity: O(N2*log(N)) (here two nested for loops so O(n2) and in between them there is __gcd(a,b) which will run in log(N) time so effective time complexity will be O(N2*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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
