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 notint coprime(int a, int b) { return (__gcd(a, b) == 1); }// Utility function to count// number of co-prime pairsint 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 pairsint 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 Codeint 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 approachimport 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 notstatic boolean coprime(int a, int b){ if (GCD(a, b) == 1) return true; return false;}// Utility function to count// number of co-prime pairsstatic 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 pairsstatic 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 Codepublic 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 approachfrom copy import deepcopyimport math# Function to check whether given# integers are co-prime or notdef coprime(a, b): return (math.gcd(a, b)) == 1# Utility function to count# number of co-prime pairsdef 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 pairsdef 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 Codeif __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 approachusing 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 notstatic bool coprime(int a, int b){ if (GCD(a, b) == 1) return true; return false;}// Utility function to count// number of co-prime pairsstatic 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 pairsstatic 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 Codepublic 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 approachfunction GCD(a,b){ return b == 0 ? a : GCD(b, a % b);}// Function to check whether given// integers are co-prime or notfunction coprime(a,b){ if (GCD(a, b) == 1) return true; return false;}// Utility function to count// number of co-prime pairsfunction 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 pairsfunction 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, d2let N = 30, d1 = 2, d2 = 3;// Function call to count// number of co-prime pairsnoOfCoPrimePairs(N, d1, d2);// This code is contributed by avanitrachhadiya2155</script> |
Output:
5
Time Complexity: O(2logN)
Auxiliary Space: O(2logN)
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!
