Given two numbers A and B where 1 <= A <= B. The task is to count the number of pairs whose elements are co-prime where pairs are formed from the sum of the digits of the elements in the given range.
Note: Two pairs are counted as distinct if at least one of the number in the pair is different. It may be assumed that the maximum digit sum can be 162.
Examples:
Input: 12 15
Output: 4
12 = 1+2 = 3
13 = 1+3 = 4
14 = 1+4 = 5
15 = 1+5 = 6
Thus pairs who are co-prime to each other are
(3, 4), (3, 5), (4, 5), (5, 6)
i.e the answer is 4.
Input: 7 10
Output: 6
Method-1:
- Consider each and every element from a to b.
- Find the sum of the digits of every element and store it into a vector.
- Consider each and every pair one by one and check if the gcd of the elements of that pair is 1.
- If yes, count that pair as it is co-prime.
- Print the count of pairs that are co-prime.
Below is the implementation of the above approach:
C++
// C++ program to count the pairs // whose sum of digits is co-prime #include <bits/stdc++.h> using namespace std; // Function to find the elements // after doing the sum of digitsint makePairs(vector<int> &pairs, int a, int b) { // Traverse from a to b for (int i = a; i <= b; i++) { // Find the sum of the digits of the elements // in the given range one by one int sumOfDigits = 0, k = i; while(k>0) { sumOfDigits += k%10; k /= 10; } if (sumOfDigits <= 162) pairs.push_back(sumOfDigits); }}// Function to count the co-prime pairsint countCoPrime(int a, int b){ vector<int> pairs; // Function to make the pairs // by doing the sum of digits makePairs(pairs, a, b); int count = 0; // Count pairs that are co-primes for(int i = 0; i < pairs.size(); i++) for (int j = i+1; j < pairs.size(); j++) if (__gcd(pairs[i], pairs[j]) == 1) count++; return count; }// Driver code int main() { int a = 12, b = 15; // Function to count the pairs cout << countCoPrime(a, b) ; return 0; } |
Java
// Java program to count the pairs // whose sum of digits is co-prime import java.util.*;class GFG{static int GCD(int a, int b) {if (b == 0) return a;return GCD(b, a % b);}// Function to find the elements // after doing the sum of digitsstatic void makePairs(Vector<Integer> pairs, int a, int b) { // Traverse from a to b for (int i = a; i <= b; i++) { // Find the sum of the digits // of the elements in the given // range one by one int sumOfDigits = 0, k = i; while(k > 0) { sumOfDigits += k % 10; k /= 10; } if (sumOfDigits <= 162) pairs.add(sumOfDigits); }}// Function to count // the co-prime pairsstatic int countCoPrime(int a, int b){ Vector<Integer> pairs = new Vector<Integer>(); // Function to make the pairs // by doing the sum of digits makePairs(pairs, a, b); int count = 0; // Count pairs that are co-primes for(int i = 0; i < pairs.size(); i++) for (int j = i+1; j < pairs.size(); j++) if (GCD(pairs.get(i), pairs.get(j)) == 1) count++; return count; }// Driver code public static void main(String args[]){ int a = 12, b = 15; // Function to count the pairs System.out.println(countCoPrime(a, b));} }// This code is contributed by Arnab Kundu |
Python3
# Python3 program to count the pairs # whose sum of digits is co-prime from math import gcd# Function to find the elements # after doing the sum of digitsdef makePairs(pairs, a, b): # Traverse from a to b for i in range(a,b+1,1): # Find the sum of the digits of the elements # in the given range one by one sumOfDigits = 0 k = i while(k>0): sumOfDigits += k%10 k = int(k / 10) if (sumOfDigits <= 162): pairs.append(sumOfDigits) # Function to count the co-prime pairsdef countCoPrime(a, b): pairs = [] # Function to make the pairs # by doing the sum of digits makePairs(pairs, a, b) count = 0 # Count pairs that are co-primes for i in range(0,len(pairs),1): for j in range(i+1,len(pairs),1): if (gcd(pairs[i], pairs[j]) == 1): count += 1 return count # Driver code if __name__ == '__main__': a = 12 b = 15 # Function to count the pairs print (countCoPrime(a, b)) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to count the pairs // whose sum of digits is co-prime using System;using System.Collections.Generic;class GFG{public static int GCD(int a, int b){ if (b == 0) { return a; } return GCD(b, a % b);}// Function to find the elements // after doing the sum of digits public static void makePairs(List<int> pairs, int a, int b){ // Traverse from a to b for (int i = a; i <= b; i++) { // Find the sum of the digits // of the elements in the given // range one by one int sumOfDigits = 0, k = i; while (k > 0) { sumOfDigits += k % 10; k /= 10; } if (sumOfDigits <= 162) { pairs.Add(sumOfDigits); } }}// Function to count // the co-prime pairs public static int countCoPrime(int a, int b){ List<int> pairs = new List<int>(); // Function to make the pairs // by doing the sum of digits makePairs(pairs, a, b); int count = 0; // Count pairs that are co-primes for (int i = 0; i < pairs.Count; i++) { for (int j = i + 1; j < pairs.Count; j++) { if (GCD(pairs[i], pairs[j]) == 1) { count++; } } } return count;}// Driver code public static void Main(string[] args){ int a = 12, b = 15; // Function to count the pairs Console.WriteLine(countCoPrime(a, b));}}// This code is contributed // by Shrikant13 |
Javascript
<script>// Javascript program to count the pairs // whose sum of digits is co-prime function GCD(a, b){ if (b == 0) return a; return GCD(b, a % b);}// Function to find the elements// after doing the sum of digitsfunction makePairs(pairs, a, b) { // Traverse from a to b for(i = a; i <= b; i++) { // Find the sum of the digits // of the elements in the given // range one by one var sumOfDigits = 0, k = i; while (k > 0) { sumOfDigits += k % 10; k = parseInt(k / 10); } if (sumOfDigits <= 162) pairs.push(sumOfDigits); }}// Function to count// the co-prime pairsfunction countCoPrime(a, b) { var pairs = []; // Function to make the pairs // by doing the sum of digits makePairs(pairs, a, b); var count = 0; // Count pairs that are co-primes for(i = 0; i < pairs.length; i++) for(j = i + 1; j < pairs.length; j++) if (GCD(pairs[i], pairs[j]) == 1) count++; return count;}// Driver codevar a = 12, b = 15;// Function to count the pairsdocument.write(countCoPrime(a, b));// This code is contributed by umadevi9616</script> |
Output
4
Method-2:
As mentioned in the question, the maximum sum can be 162. So, find out the frequency of numbers having their digit sum from 1 to 162 in range A to B and store the frequency in the array. Later, find the answer using this frequency.
Since,
Number, Frequency
1, 0
2, 0
3, 1
4, 1
5, 1
6, 1
7, 0
8, 0
., .
., .
162, 0
Thus Number of gcd pairs = freq(3)*freq(4) + freq(3)*freq(5) + freq(4)*freq(5) + freq(5)* freq(6)
= 1+1+1+1
= 4
Thus pairs who are co-prime to each other are (3,4), (3,5), (4,5), (5,6) i.e the answer is 4.
Below is the required implementation:
C++
// C++ program to count the pairs// whose sum of digits is co-prime#include <bits/stdc++.h>#define ll long long intusing namespace std;// Recursive function to return the frequency// of numbers having their sum of digits ill recursive(ll idx, ll sum, ll tight, string st, ll dp[20][2][166], ll num){ if (idx == num) // Returns 1 or 0 return sum == 0; // Returns value of the dp if already stored if (dp[idx][tight][sum] != -1) return dp[idx][tight][sum]; bool newTight; ll ans = 0; ll d; // Loop from digit 0 to 9 for (d = 0; d < 10; ++d) { newTight = false; if (tight && st[idx] - '0' < d) continue; // To change the tight to 1 if (tight && st[idx] - '0' == d) newTight = true; // Calling the recursive function to find the frequency if (sum >= d) ans += recursive(idx + 1, sum - d, newTight, st, dp, num); } return dp[idx][tight][sum] = ans;}// Function to find out frequency of numbers// from 1 to N having their sum of digits// from 1 to 162 and store them in arrayvector<ll> formArray(ll N){ ll dp[20][2][166]; memset(dp, -1, sizeof dp); // Number to string conversion ostringstream x; x << N; string st = x.str(); ll num = st.size(); vector<ll> arr; for (int i = 1; i <= 162; ++i) { // Calling the recursive function // and pushing it into array arr.push_back(recursive(0, i, 1, st, dp, num)); } return arr;}// Function to find the pairsll findPair(ll a, ll b){ // Calling the formArray function of a-1 numbers vector<ll> arr_smaller = formArray(a - 1); // Calling the formArray function of b numbers vector<ll> arr_greater = formArray(b); // Subtracting the frequency of higher number array with lower // number array and thus finding the range of // numbers from a to b having sum from 1 to 162 for (int i = 0; i < arr_greater.size(); ++i) arr_greater[i] -= arr_smaller[i]; int ans = 0; for (int i = 1; i <= 162; ++i) { for (int j = i + 1; j <= 162; ++j) { // To find out total number of pairs // which are co-prime if (__gcd(i, j) == 1) ans = (ans + arr_greater[i - 1] * arr_greater[j - 1]); } } return ans;}// Driver codeint main(){ ll a = 12, b = 15; // Function to count the pairs cout << findPair(a, b); return 0;} |
Java
// Java program to count the pairs// whose sum of digits is co-primeimport java.io.*;import java.util.*;class GFG{ static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Recursive function to return the frequency // of numbers having their sum of digits i static long recursive(long idx, long sum, long tight, String st, long[][][] dp, long num) { if (idx == num) { // Returns 1 or 0 return sum == 0 ? 1 : 0; } // Returns value of the dp if already stored if (dp[(int)idx][(int)tight][(int)sum] != -1) return dp[(int)idx][(int)tight][(int)sum]; long newTight; long ans = 0; long d; // Loop from digit 0 to 9 for (d = 0; d < 10; ++d) { newTight = 0; if (tight == 1 && st.charAt((int)idx) - '0' < d) continue; // To change the tight to 1 if (tight == 1 && st.charAt((int)idx) - '0' == d) newTight = 1; // Calling the recursive function to find the frequency if (sum >= d) ans += recursive(idx + 1, sum - d, (int)newTight, st, dp, num); } return dp[(int)idx][(int)tight][(int)sum] = ans; } // Function to find out frequency of numbers // from 1 to N having their sum of digits // from 1 to 162 and store them in array static ArrayList<Long> formArray(long N) { long[][][] dp = new long[20][2][166]; for (long[][] innerRow: dp) { for (long[] innerInnerRow: innerRow) { Arrays.fill(innerInnerRow, -1); } } // Number to string conversion String st = String.valueOf(N); long num = st.length(); ArrayList<Long> arr = new ArrayList<Long>(); for (int i = 1; i <= 162; ++i) { // Calling the recursive function // and pushing it into array arr.add(recursive(0, i, 1, st, dp, num)); } return arr; } // Function to find the pairs static long findPair(long a, long b) { // Calling the formArray function of a-1 numbers ArrayList<Long> arr_smaller = formArray(a - 1); // Calling the formArray function of b numbers ArrayList<Long> arr_greater = formArray(b); // Subtracting the frequency of higher number array with lower // number array and thus finding the range of // numbers from a to b having sum from 1 to 162 for (int i = 0; i < arr_greater.size(); ++i) { arr_greater.set(i,arr_greater.get(i)-arr_smaller.get(i)); } long ans = 0; for (int i = 1; i <= 162; ++i) { for (int j = i + 1; j <= 162; ++j) { // To find out total number of pairs // which are co-prime if (gcd(i, j) == 1) { ans = (ans + arr_greater.get(i-1) * arr_greater.get(j-1)); } } } return ans; } // Driver code public static void main (String[] args) { long a = 12, b = 15; // Function to count the pairs System.out.println(findPair(a, b)); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to count # the pairs whose sum of # digits is co-primeimport math# Recursive function to# return the frequency of # numbers having their sum # of digits idef recursive(idx, sum, tight, st, dp, num): if (idx == num): # Returns 1 or 0 return sum == 0 # Returns value of the dp # if already stored if (dp[idx][tight][sum] != -1): return dp[idx][tight][sum] ans = 0 # Loop from digit 0 to 9 for d in range(10): newTight = False if (tight and ord(st[idx]) - ord('0') < d): continue # To change the tight to 1 if (tight and ord(st[idx]) - ord('0') == d): newTight = True # Calling the recursive # function to find the # frequency if (sum >= d): ans += recursive(idx + 1, sum - d, newTight, st, dp, num) dp[idx][tight][sum] = ans return dp[idx][tight][sum]# Function to find out frequency # of numbers from 1 to N having # their sum of digits from 1 to # 162 and store them in arraydef formArray(N): dp = [[[-1 for x in range(166)] for y in range(2)] for z in range(20)] # Number to string conversion st = str(N) num = len(st) arr = [] for i in range(1, 163): # Calling the recursive function # and pushing it into array arr.append(recursive(0, i, 1, st, dp, num)) return arr# Function to find the pairsdef findPair(a, b): # Calling the formArray # function of a-1 numbers arr_smaller = formArray(a - 1) # Calling the formArray # function of b numbers arr_greater = formArray(b) # Subtracting the frequency of # higher number array with lower # number array and thus finding # the range of numbers from a to # b having sum from 1 to 162 for i in range(len(arr_greater)): arr_greater[i] -= arr_smaller[i] ans = 0 for i in range(1, 163): for j in range(i + 1, 163): # To find out total number # of pairs which are co-prime if (math.gcd(i, j) == 1): ans = (ans + arr_greater[i - 1] * arr_greater[j - 1]) return ans# Driver codeif __name__ == "__main__": a = 12 b = 15 # Function to count the pairs print(findPair(a, b))# This code is contributed by Chitranayal |
C#
// C# program to count the pairs// whose sum of digits is co-primeusing System;using System.Collections.Generic;class GFG{ static int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b); } // Recursive function to return the frequency// of numbers having their sum of digits istatic long recursive(long idx, long sum, long tight, string st, long[,,] dp, long num){ if (idx == num) { // Returns 1 or 0 return sum == 0 ? 1 : 0; } // Returns value of the dp if already stored if (dp[(int)idx, (int)tight, (int)sum] != -1) return dp[(int)idx, (int)tight, (int)sum]; long newTight; long ans = 0; long d; // Loop from digit 0 to 9 for (d = 0; d < 10; ++d) { newTight = 0; if (tight == 1 && st[((int)idx)] - '0' < d) continue; // To change the tight to 1 if (tight == 1 && st[((int)idx)] - '0' == d) newTight = 1; // Calling the recursive function to // find the frequency if (sum >= d) ans += recursive(idx + 1, sum - d, (int)newTight, st, dp, num); } return dp[(int)idx, (int)tight, (int)sum] = ans;} // Function to find out frequency of numbers// from 1 to N having their sum of digits// from 1 to 162 and store them in arraystatic List<long> formArray(long N){ long[,,] dp = new long[20, 2, 166]; for(int i = 0; i < 20; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 166; k++) { dp[i, j, k] = -1; } } } // Number to string conversion string st = N.ToString(); long num = st.Length; List<long> arr = new List<long>(); for (int i = 1; i <= 162; ++i) { // Calling the recursive function // and pushing it into array arr.Add(recursive(0, i, 1, st, dp, num)); } return arr;}// Function to find the pairsstatic long findPair(long a, long b){ // Calling the formArray function of a-1 numbers List<long> arr_smaller = formArray(a - 1); // Calling the formArray function of b numbers List<long> arr_greater = formArray(b); // Subtracting the frequency of higher number // array with lower number array and thus // finding the range of numbers from a to b // having sum from 1 to 162 for(int i = 0; i < arr_greater.Count; ++i) { arr_greater[i] = arr_greater[i] - arr_smaller[i]; } long ans = 0; for(int i = 1; i <= 162; ++i) { for(int j = i + 1; j <= 162; ++j) { // To find out total number of pairs // which are co-prime if (gcd(i, j) == 1) { ans = (ans + arr_greater[i - 1] * arr_greater[j - 1]); } } } return ans;}// Driver codestatic public void Main(){ long a = 12, b = 15; // Function to count the pairs Console.WriteLine(findPair(a, b));}}// This code is contributed by rag2127 |
Javascript
<script>// Javascript program to count the pairs// whose sum of digits is co-primefunction gcd(a,b){ if (b == 0) return a; return gcd(b, a % b); }// Recursive function to return the frequency// of numbers having their sum of digits ifunction recursive(idx,sum,tight,st,dp, num){ if (idx == num) { // Returns 1 or 0 return sum == 0 ? 1 : 0; } // Returns value of the dp if already stored if (dp[idx][tight][sum] != -1) return dp[idx][tight][sum]; let newTight; let ans = 0; let d; // Loop from digit 0 to 9 for (d = 0; d < 10; ++d) { newTight = 0; if (tight == 1 && st[idx].charCodeAt(0) - '0'.charCodeAt(0) < d) continue; // To change the tight to 1 if (tight == 1 && st[idx].charCodeAt(0) - '0'.charCodeAt(0) == d) newTight = 1; // Calling the recursive function to find the frequency if (sum >= d) ans += recursive(idx + 1, sum - d, newTight, st, dp, num); } return dp[idx][tight][sum] = ans;}// Function to find out frequency of numbers // from 1 to N having their sum of digits // from 1 to 162 and store them in arrayfunction formArray(N){ let dp = new Array(20); for(let i=0;i<20;i++) { dp[i]=new Array(2); for(let j=0;j<2;j++) { dp[i][j]=new Array(166); for(let k=0;k<166;k++) { dp[i][j][k]=-1; } } } // Number to string conversion let st = (N).toString(); let num = st.length; let arr = []; for (let i = 1; i <= 162; ++i) { // Calling the recursive function // and pushing it into array arr.push(recursive(0, i, 1, st, dp, num)); } return arr;}// Function to find the pairsfunction findPair(a,b){ // Calling the formArray function of a-1 numbers let arr_smaller = formArray(a - 1); // Calling the formArray function of b numbers let arr_greater = formArray(b); // Subtracting the frequency of higher number array with lower // number array and thus finding the range of // numbers from a to b having sum from 1 to 162 for (let i = 0; i < arr_greater.length; ++i) { arr_greater[i] -= arr_smaller[i]; } let ans = 0; for (let i = 1; i <= 162; ++i) { for (let j = i + 1; j <= 162; ++j) { // To find out total number of pairs // which are co-prime if (gcd(i, j) == 1) { ans = (ans + arr_greater[i-1] * arr_greater[j-1]); } } } return ans;}// Driver codelet a = 12, b = 15; // Function to count the pairsdocument.write(findPair(a, b));// This code is contributed by ab2127</script> |
Output
4
Approach#3: Using sieve of Eratosthenes
this approach to solve this problem is to use the Sieve of Eratosthenes to find all prime numbers up to a certain limit, and then iterate through the given range to count the number of pairs that are co-prime to each other.
Algorithm
1. Implement the Sieve of Eratosthenes to find all prime numbers up to the maximum sum of digits in the given range.
2. Iterate through the given range and for each number, find the sum of its digits.
3. For each pair of numbers in the given range, check if their sum of digits is co-prime to each other.
4. Return the total count of co-prime pairs.
C++
// C++ code addition #include <iostream>#include <vector>#include <cmath>using namespace std;int sumDigits(int n) { // calculate the sum of digits of a number int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum;}vector<bool> sieve(int n) { // initialize array of booleans for primes vector<bool> primes(n+1, true); primes[0] = primes[1] = false; // use sieve of Eratosthenes to mark non-primes for (int i = 2; i <= sqrt(n); i++) { if (primes[i]) { for (int j = i*i; j <= n; j += i) { primes[j] = false; } } } return primes;}int gcd(int a, int b) { // calculate GCD using Euclid's algorithm if (b == 0) { return a; } else { return gcd(b, a % b); }}int count_coprime_pairs(int l, int r) { // calculate the maximum possible sum of digits // from l to r int max_sum = 0; for (int i = l; i <= r; i++) { max_sum = max(max_sum, sumDigits(i)); } // generate primes using the sieve of Eratosthenes vector<bool> primes = sieve(max_sum); int count = 0; // count coprime pairs for (int i = l; i <= r; i++) { for (int j = i+1; j <= r; j++) { if (gcd(sumDigits(i), sumDigits(j)) == 1) { count += 1; } } } return count;}int main() { int l = 12; int r = 15; int count = count_coprime_pairs(l, r); cout << count << endl; return 0;}// The code is contributed by Nidhi goel. |
Java
// Java Program for the above approachimport java.util.*;public class GFG { public static int sumDigits(int n) { // calculate the sum of digits of a number int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } public static boolean[] sieve(int n) { // initialize array of booleans for primes boolean[] primes = new boolean[n + 1]; Arrays.fill(primes, true); primes[0] = primes[1] = false; // use sieve of Eratosthenes to mark non-primes for (int i = 2; i <= Math.sqrt(n); i++) { if (primes[i]) { for (int j = i * i; j <= n; j += i) { primes[j] = false; } } } return primes; } public static int gcd(int a, int b) { // calculate GCD using Euclid's algorithm if (b == 0) { return a; } else { return gcd(b, a % b); } } public static int count_coprime_pairs(int l, int r) { // calculate the maximum possible sum of digits from l to r int max_sum = 0; for (int i = l; i <= r; i++) { max_sum = Math.max(max_sum, sumDigits(i)); } // generate primes using the sieve of Eratosthenes boolean[] primes = sieve(max_sum); int count = 0; // count coprime pairs for (int i = l; i <= r; i++) { for (int j = i + 1; j <= r; j++) { if (gcd(sumDigits(i), sumDigits(j)) == 1) { count += 1; } } } return count; } public static void main(String[] args) { int l = 12; int r = 15; int count = count_coprime_pairs(l, r); System.out.println(count); }}// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
Python3
def sieve(n): primes = [True] * (n+1) primes[0] = primes[1] = False for i in range(2, int(n**0.5)+1): if primes[i]: for j in range(i*i, n+1, i): primes[j] = False return primesdef gcd(a, b): if b == 0: return a else: return gcd(b, a % b)def count_coprime_pairs(l, r): max_sum = sum(int(digit) for digit in str(r)) primes = sieve(max_sum) count = 0 for i in range(l, r+1): for j in range(i+1, r+1): if gcd(sum(int(digit) for digit in str(i)), sum(int(digit) for digit in str(j))) == 1: count += 1 return countl = 12r = 15count = count_coprime_pairs(l, r)print(count) |
C#
using System;using System.Collections.Generic;class Program { static int SumDigits(int n) { // calculate the sum of digits of a number int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } static bool[] Sieve(int n) { // initialize array of booleans for primes bool[] primes = new bool[n+1]; for (int i = 2; i <= n; i++) { primes[i] = true; } // use sieve of Eratosthenes to mark non-primes for (int i = 2; i*i <= n; i++) { if (primes[i]) { for (int j = i*i; j <= n; j += i) { primes[j] = false; } } } return primes; } static int GCD(int a, int b) { // calculate GCD using Euclid's algorithm if (b == 0) { return a; } else { return GCD(b, a % b); } } static int CountCoprimePairs(int l, int r) { // calculate the maximum possible sum of digits // from l to r int max_sum = 0; for (int i = l; i <= r; i++) { max_sum = Math.Max(max_sum, SumDigits(i)); } // generate primes using the sieve of Eratosthenes bool[] primes = Sieve(max_sum); int count = 0; // count coprime pairs for (int i = l; i <= r; i++) { for (int j = i+1; j <= r; j++) { if (GCD(SumDigits(i), SumDigits(j)) == 1) { count += 1; } } } return count; } static void Main() { int l = 12; int r = 15; int count = CountCoprimePairs(l, r); Console.WriteLine(count); }} |
Javascript
function sieve(n) { // initialize array of booleans for primes let primes = Array(n+1).fill(true); primes[0] = primes[1] = false; // use sieve of Eratosthenes to mark non-primes for (let i = 2; i <= Math.sqrt(n); i++) { if (primes[i]) { for (let j = i*i; j <= n; j += i) { primes[j] = false; } } } return primes;}function gcd(a, b) { // calculate GCD using Euclid's algorithm if (b == 0) { return a; } else { return gcd(b, a % b); }}function count_coprime_pairs(l, r) { // calculate the maximum possible sum of digits // from l to r let max_sum = 0; for (let i = l; i <= r; i++) { max_sum = Math.max(max_sum, sumDigits(i)); } // generate primes using the sieve of Eratosthenes let primes = sieve(max_sum); let count = 0; // count coprime pairs for (let i = l; i <= r; i++) { for (let j = i+1; j <= r; j++) { if (gcd(sumDigits(i), sumDigits(j)) == 1) { count += 1; } } } return count;}function sumDigits(n) { // calculate the sum of digits of a number let sum = 0; while (n > 0) { sum += n % 10; n = Math.floor(n / 10); } return sum;}let l = 12;let r = 15;let count = count_coprime_pairs(l, r);console.log(count); |
Output
4
Time Complexity: O(N^2 * log(logN)), where N is the maximum sum of digits in the given range.
Space Complexity: O(N), for storing the primes up to the maximum sum of digits.
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!
