Given an integer K and a range [L, R], the task is to count the quadruplet pairs from the given range having gcd equal to K.
Examples:
Input: L = 1, R = 5, K = 3
Output: 1
(3, 3, 3, 3) is the only valid quadruplet with gcd = 3
Input: L = 2, R = 24, K = 5
Output: 239
Naive approach: We can iterate over all the numbers with four loops and for every quadruplet pair check whether its gcd is equal to K.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of quadruplets having gcd = kint countQuadruplets(int l, int r, int k){ // To store the required count int count = 0; // Check every quadruplet pair // whether its gcd is k for (int u = l; u <= r; u++) { for (int v = l; v <= r; v++) { for (int w = l; w <= r; w++) { for (int x = l; x <= r; x++) { if (__gcd(__gcd(u, v), __gcd(w, x)) == k) count++; } } } } // Return the required count return count;}// Driver codeint main(){ int l = 1, r = 10, k = 2; cout << countQuadruplets(l, r, k); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function to return // the gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k static int countQuadruplets(int l, int r, int k) { // To store the required count int count = 0; // Check every quadruplet pair // whether its gcd is k for (int u = l; u <= r; u++) { for (int v = l; v <= r; v++) { for (int w = l; w <= r; w++) { for (int x = l; x <= r; x++) { if (gcd(gcd(u, v), gcd(w, x)) == k) count++; } } } } // Return the required count return count; } // Driver code public static void main(String[] args) { int l = 1, r = 10, k = 2; System.out.println(countQuadruplets(l, r, k)); }}// This code is contributed by jit_t. |
Python 3
# Python 3 implementation of the approachfrom math import gcd# Function to return the count# of quadruplets having gcd = kdef countQuadruplets(l, r, k): # To store the required count count = 0 # Check every quadruplet pair # whether its gcd is k for u in range(l, r + 1 ,1): for v in range(l, r + 1, 1): for w in range(l, r + 1, 1): for x in range(l, r + 1, 1): if (gcd(gcd(u, v), gcd(w, x)) == k): count += 1 # Return the required count return count# Driver codeif __name__ == '__main__': l = 1 r = 10 k = 2 print(countQuadruplets(l, r, k)) # This code is contributed # by Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG { // Function to return // the gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k static int countQuadruplets(int l, int r, int k) { // To store the required count int count = 0; // Check every quadruplet pair // whether its gcd is k for (int u = l; u <= r; u++) { for (int v = l; v <= r; v++) { for (int w = l; w <= r; w++) { for (int x = l; x <= r; x++) { if (gcd(gcd(u, v), gcd(w, x)) == k) count++; } } } } // Return the required count return count; } // Driver code static public void Main() { int l = 1, r = 10, k = 2; Console.WriteLine(countQuadruplets(l, r, k)); }}// This code is contributed by ajit. |
Javascript
<script>// javascript implementation of the approach // Function to return // the gcd of a and b function gcd(a , b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k function countQuadruplets(l , r , k) { // To store the required count var count = 0; // Check every quadruplet pair // whether its gcd is k for (u = l; u <= r; u++) { for (v = l; v <= r; v++) { for (w = l; w <= r; w++) { for (x = l; x <= r; x++) { if (gcd(gcd(u, v), gcd(w, x)) == k) count++; } } } } // Return the required count return count; } // Driver code var l = 1, r = 10, k = 2; document.write(countQuadruplets(l, r, k));// This code is contributed by todaysgaurav</script> |
Output:
607
Time Complexity: O((r – l)4)
Auxiliary Space: O(1)
Efficient approach:
- Find the GCD of every possible pair (x, y) in the given range.
- Count the frequencies of every possible GCD value.
- After that if the GCD value of two numbers is k then increment count by frequency[i] * frequency[j].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return// the gcd of a and bint gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// Function to return the count// of quadruplets having gcd = kint countQuadruplets(int l, int r, int k){ int frequency[r + 1] = { 0 }; // Count the frequency of every possible gcd // value in the range for (int i = l; i <= r; i++) { for (int j = l; j <= r; j++) { frequency[gcd(i, j)]++; } } // To store the required count long long answer = 0; // Calculate the answer using frequency values for (int i = 1; i <= r; i++) { for (int j = 1; j <= r; j++) { if (gcd(i, j) == k) { answer += (frequency[i] * frequency[j]); } } } // Return the required count return answer;}// Driver codeint main(){ int l = 1, r = 10, k = 2; cout << countQuadruplets(l, r, k); return 0;} |
Java
// Java implementation of the approach class GFG{ // Function to return // the gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k static int countQuadruplets(int l, int r, int k) { int frequency[]= new int[r + 1] ; // Count the frequency of every possible gcd // value in the range for (int i = l; i <= r; i++) { for (int j = l; j <= r; j++) { frequency[gcd(i, j)]++; } } // To store the required count long answer = 0; // Calculate the answer using frequency values for (int i = 1; i <= r; i++) { for (int j = 1; j <= r; j++) { if (gcd(i, j) == k) { answer += (frequency[i] * frequency[j]); } } } // Return the required count return (int)answer; } // Driver code public static void main(String args[]){ int l = 1, r = 10, k = 2; System.out.println(countQuadruplets(l, r, k)); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# Function to return# the gcd of a and bdef gcd(a, b): if (b == 0): return a; return gcd(b, a % b);# Function to return the count# of quadruplets having gcd = kdef countQuadruplets(l, r, k): frequency = [0] * (r + 1); # Count the frequency of every possible gcd # value in the range for i in range(l, r + 1): for j in range(l, r + 1): frequency[gcd(i, j)] += 1; # To store the required count answer = 0; # Calculate the answer using frequency values for i in range(l, r + 1): for j in range(l, r + 1): if (gcd(i, j) == k): answer += (frequency[i] * frequency[j]); # Return the required count return answer;# Driver codeif __name__ == '__main__': l, r, k = 1, 10, 2; print(countQuadruplets(l, r, k));# This code is contributed by Rajput-Ji |
C#
// C# implementation of the approach using System;class GFG{ // Function to return // the gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k static int countQuadruplets(int l, int r, int k) { int []frequency= new int[r + 1] ; // Count the frequency of every possible gcd // value in the range for (int i = l; i <= r; i++) { for (int j = l; j <= r; j++) { frequency[gcd(i, j)]++; } } // To store the required count long answer = 0; // Calculate the answer using frequency values for (int i = 1; i <= r; i++) { for (int j = 1; j <= r; j++) { if (gcd(i, j) == k) { answer += (frequency[i] * frequency[j]); } } } // Return the required count return (int)answer; } // Driver code static public void Main (){ int l = 1, r = 10, k = 2; Console.WriteLine(countQuadruplets(l, r, k)); }} // This code is contributed by @ajit_00023 |
Javascript
<script> // Javascript implementation of the approach // Function to return // the gcd of a and b function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return the count // of quadruplets having gcd = k function countQuadruplets(l, r, k) { let frequency= new Array(r + 1); frequency.fill(0); // Count the frequency of every possible gcd // value in the range for (let i = l; i <= r; i++) { for (let j = l; j <= r; j++) { frequency[gcd(i, j)]++; } } // To store the required count let answer = 0; // Calculate the answer using frequency values for (let i = 1; i <= r; i++) { for (let j = 1; j <= r; j++) { if (gcd(i, j) == k) { answer += (frequency[i] * frequency[j]); } } } // Return the required count return answer; } let l = 1, r = 10, k = 2; document.write(countQuadruplets(l, r, k)); </script> |
Output:
607
Time Complexity: O(r2)
Auxiliary Space: O(r)
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!
