Given an integer N and two integers D1 and D2 ( < 10), the task is to find the number of co-prime pairs less than or equal to N consisting of only digits D1 and D2.
Examples:
Input: N = 30, D1 = 2, D2 = 3
Output: 5
Explanation:
All possible pairs of numbers upto 30 having digits 2 and 3 which are co-prime to each other are (2, 3), (2, 23), (3, 22), (3, 23), (22, 23) .Input: N = 100, D1 = 5, D2 = 6
Output: 8
Explanation:
All possible pairs of numbers upto 100 having digits 5 and 6 which are co-prime to each other are (5, 6), (5, 56), (5, 66), (6, 55), (6, 65), (55, 56), (56, 65), (65, 66).
Approach: The idea to solve this problem is based on the following observations:
Observation:
- Find and append every number consisting only given two digits which are less than or equal to N into a list.
- Now it’s easy to find the number of unordered pairs which are co-primes.
- Note that there can be maximum 1 + 2 + 22 + 23 + 24 + ………210= 2047 numbers in the list i.e. Overall Time Complexity cannot exceed O(2047 * 2047), as the maximum no. of digits possible is 9.
Follow the steps below to solve the problem:
- Initialize an empty list, say l, and append the given two digits as a string into the list.
- Sort the list.
- Initialize two lists, say total and temp2 for further use.
- Iterate until l[0] < 10:
- Append the given two digits as a string to all the elements present in the list l.
- Keep updating l in the way shown below:
- [2, 3] -> [‘2’ + ‘2’, ‘2’ + ‘3’, ‘3’ + ‘2’, ‘3’ + ‘3’]
- [22, 23, 32, 33] – > [’22’ + ‘2’, ’22’ + ‘3’, ’23’ + ‘2’, ’23’ + ‘3’, ’32’ + ‘2’, ’32’ + ‘3’, ’33’ + ‘2’, ’33’ + ‘3’] and so on.
- Define a function numOfPairs() which returns the count of unordered co-prime pairs.
- Print the count returned by the above function as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether given // integers are co-prime or not int coprime( int a, int b) { return (__gcd(a, b) == 1); } // Utility function to count // number of co-prime pairs int numOfPairs(vector<string> arr, int N) { int count = 0; // Traverse the array for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // If co-prime if (coprime(stoi(arr[i]), stoi(arr[j]))) { // Increment count count = count + 1; } } } // Return count return count; } // Function to count number // of co-prime pairs int noOfCoPrimePairs( int N, int d1, int d2) { // Stores digits in string form vector<string> l; l.push_back(to_string(d1)); l.push_back(to_string(d2)); // Sort the list sort(l.begin(), l.end()); if (N < stoi(l[1])) return 0; // Keep two copies of list l vector<string> total = l; vector<string> temp2 = l; int flag = 0; vector<string> temp3; // Generate 2 digit numbers // using d1 and d2 while (l[0].length() < 10) { for ( int i = 0; i < l.size(); i++) { for ( int j = 0; j < 2; j++) { // If current number // does not exceed N if (stoi(l[i] + temp2[j]) > N) { flag = 1; break ; } total.push_back(l[i] + temp2[j]); temp3.push_back(l[i] + temp2[j]); } if (flag == 1) break ; } if (flag == 1) break ; l = temp3; vector<string> temp3; } // Stores length of list int lenOfTotal = total.size(); // Stores number of co-prime pairs int ans = numOfPairs(total, lenOfTotal); // Print number of co-prime pairs cout << (ans); } // Driver Code int main() { // Given value of N, d1, d2 int N = 30, d1 = 2, d2 = 3; // Function call to count // number of co-prime pairs noOfCoPrimePairs(N, d1, d2); } // This code is contributed by ukasp. |
Java
// Java program for the above approach import java.util.*; class GFG{ static int GCD( int a, int b) { return b == 0 ? a : GCD(b, a % b); } // Function to check whether given // integers are co-prime or not static boolean coprime( int a, int b) { if (GCD(a, b) == 1 ) return true ; return false ; } // Utility function to count // number of co-prime pairs static int numOfPairs(ArrayList<String> arr, int N) { int count = 0 ; // Traverse the array for ( int i = 0 ; i < N - 1 ; i++) { for ( int j = i + 1 ; j < N; j++) { // If co-prime if (coprime(Integer.parseInt(arr.get(i)), Integer.parseInt(arr.get(j)))) { // Increment count count = count + 1 ; } } } // Return count return count; } // Function to count number // of co-prime pairs static void noOfCoPrimePairs( int N, int d1, int d2) { // Stores digits in string form ArrayList<String> l = new ArrayList<String>(); l.add(Integer.toString(d1)); l.add(Integer.toString(d2)); // Sort the list Collections.sort(l); if (N < Integer.parseInt(l.get( 1 ))) return ; // Keep two copies of list l ArrayList<String> total = new ArrayList<String>(l); ArrayList<String> temp2 = new ArrayList<String>(l); int flag = 0 ; ArrayList<String> temp3 = new ArrayList<String>(l); // Generate 2 digit numbers // using d1 and d2 while (l.get( 0 ).length() < 10 ) { for ( int i = 0 ; i < l.size(); i++) { for ( int j = 0 ; j < 2 ; j++) { // If current number // does not exceed N if (Integer.parseInt(l.get(i) + temp2.get(j)) > N) { flag = 1 ; break ; } total.add(l.get(i) + temp2.get(j)); temp3.add(l.get(i) + temp2.get(j)); } if (flag == 1 ) break ; } if (flag == 1 ) break ; l = temp3; temp3.clear(); } // Stores length of list int lenOfTotal = total.size(); // Stores number of co-prime pairs int ans = numOfPairs(total, lenOfTotal); // Print number of co-prime pairs System.out.print(ans); } // Driver Code public static void main(String args[]) { // Given value of N, d1, d2 int N = 30 , d1 = 2 , d2 = 3 ; // Function call to count // number of co-prime pairs noOfCoPrimePairs(N, d1, d2); } } // This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approach from copy import deepcopy import math # Function to check whether given # integers are co-prime or not def coprime(a, b): return (math.gcd(a, b)) = = 1 # Utility function to count # number of co-prime pairs def numOfPairs(arr, N): count = 0 # Traverse the array for i in range ( 0 , N - 1 ): for j in range (i + 1 , N): # If co-prime if (coprime( int (arr[i]), int (arr[j]))): # Increment count count = count + 1 # Return count return count # Function to count number # of co-prime pairs def noOfCoPrimePairs(N, d1, d2): # Stores digits in string form l = [] l.append( str (d1)) l.append( str (d2)) # Sort the list l.sort() if int (N) < int (l[ 1 ]): return 0 # Keep two copies of list l total = temp2 = deepcopy(l) flag = 0 temp3 = [] # Generate 2 digit numbers # using d1 and d2 while len (l[ 0 ]) < 10 : for i in range ( len (l)): for j in range ( 2 ): # If current number # does not exceed N if int (l[i] + temp2[j]) > int (N): flag = 1 break total.append(l[i] + temp2[j]) temp3.append(l[i] + temp2[j]) if flag = = 1 : break if flag = = 1 : break l = deepcopy(temp3) temp3 = [] # Stores length of list lenOfTotal = len (total) # Stores number of co-prime pairs ans = numOfPairs(total, lenOfTotal) # Print number of co-prime pairs print (ans) # Driver Code if __name__ = = "__main__" : # Given value of N, d1, d2 N = 30 d1 = 2 d2 = 3 # Function call to count # number of co-prime pairs noOfCoPrimePairs(N, d1, d2) |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int GCD( int a, int b) { return b == 0 ? a : GCD(b, a % b); } // Function to check whether given // integers are co-prime or not static bool coprime( int a, int b) { if (GCD(a, b) == 1) return true ; return false ; } // Utility function to count // number of co-prime pairs static int numOfPairs(List< string > arr, int N) { int count = 0; // Traverse the array for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // If co-prime if (coprime(Int32.Parse(arr[i]), Int32.Parse(arr[j]))) { // Increment count count = count + 1; } } } // Return count return count; } // Function to count number // of co-prime pairs static void noOfCoPrimePairs( int N, int d1, int d2) { // Stores digits in string form List< string > l = new List< string >(); l.Add(d1.ToString()); l.Add(d2.ToString()); // Sort the list l.Sort(); if (N < Int32.Parse(l[1])) return ; // Keep two copies of list l List< string > total = new List< string >(l); List< string > temp2 = new List< string >(l); int flag = 0; List< string > temp3 = new List< string >(); // Generate 2 digit numbers // using d1 and d2 while (l[0].Length < 10) { for ( int i = 0; i < l.Count; i++) { for ( int j = 0; j < 2; j++) { // If current number // does not exceed N if (Int32.Parse(l[i] + temp2[j]) > N) { flag = 1; break ; } total.Add(l[i] + temp2[j]); temp3.Add(l[i] + temp2[j]); } if (flag == 1) break ; } if (flag == 1) break ; l = temp3; temp3.Clear(); } // Stores length of list int lenOfTotal = total.Count; // Stores number of co-prime pairs int ans = numOfPairs(total, lenOfTotal); // Print number of co-prime pairs Console.WriteLine(ans); } // Driver Code public static void Main() { // Given value of N, d1, d2 int N = 30, d1 = 2, d2 = 3; // Function call to count // number of co-prime pairs noOfCoPrimePairs(N, d1, d2); } } // This code is contributed by ipg2016107 |
Javascript
<script> // JavaScript program for the above approach function GCD(a,b) { return b == 0 ? a : GCD(b, a % b); } // Function to check whether given // integers are co-prime or not function coprime(a,b) { if (GCD(a, b) == 1) return true ; return false ; } // Utility function to count // number of co-prime pairs function numOfPairs(arr,N) { let count = 0; // Traverse the array for (let i = 0; i < N - 1; i++) { for (let j = i + 1; j < N; j++) { // If co-prime if (coprime(parseInt(arr[i]), parseInt(arr[j]))) { // Increment count count = count + 1; } } } // Return count return count; } // Function to count number // of co-prime pairs function noOfCoPrimePairs(N,d1,d2) { // Stores digits in string form let l = []; l.push(d1.toString()); l.push(d2.toString()); // Sort the list l.sort(); if (N < parseInt(l[1])) return ; // Keep two copies of list l let total = [...l]; let temp2 = [...l]; let flag = 0; let temp3 = []; // Generate 2 digit numbers // using d1 and d2 while (l[0].length < 10) { for (let i = 0; i < l.length; i++) { for (let j = 0; j < 2; j++) { // If current number // does not exceed N if (parseInt(l[i] + temp2[j]) > N) { flag = 1; break ; } total.push(l[i] + temp2[j]); temp3.push(l[i] + temp2[j]); } if (flag == 1) break ; } if (flag == 1) break ; l = [...temp3]; temp3=[]; } // Stores length of list let lenOfTotal = total.length; // Stores number of co-prime pairs let ans = numOfPairs(total, lenOfTotal); // Print number of co-prime pairs document.write(ans); } // Driver Code // Given value of N, d1, d2 let N = 30, d1 = 2, d2 = 3; // Function call to count // number of co-prime pairs noOfCoPrimePairs(N, d1, d2); // This code is contributed by avanitrachhadiya2155 </script> |
5
Time Complexity: O(2logN)
Auxiliary Space: O(2logN)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!