Kth number from the set of multiples of numbers A, B and C

Given four integers A, B, C and K. Assume that all the multiples of A, B and C are stored in a set in sorted order with no duplicates, now the task is to find the Kth element from that set.
Examples:
Input: A = 1, B = 2, C = 3, K = 4
Output: 4
The required set is {1, 2, 3, 4, 5, …}
Input: A = 2, B = 4, C = 5, K = 5
Output: 8
Approach: Binary Search can be used here on K to find the Kth number in the set. Let’s find the Kth number if this was a multiple of A.
Apply Binary search on the multiples of A, starting from 1 to K (as there may be utmost K multiples of A to find the Kth number in the required set).
Now, for a value mid, the required multiple of A will be A * mid (say X). Now the task is to find whether this is the Kth number of the required set. It can be found as shown below:
Find the number of multiples of A less than X say A1
Find the number of multiples of B less than X say B1
Find the number of multiples of C less than X say C1
Find the number of multiples of lcm(A, B) (Divisible by both A and B) less than X say AB1
Find the number of multiples of lcm(B, C) less than X say BC1
Find the number of multiples of lcm(C, A) less than X say CA1
Find the number of multiples of lcm(A, B, C) less than X say ABC1
Now, the count of numbers in the required set less than X will be A1 + B1 + C1 – AB1 – BC1 – CA1 + ABC1 by the principle of Inclusion and Exclusion.
If count = K – 1, then X is the required answer.
If count < K – 1 then that multiple is greater than X implies set start = mid + 1 else set end = mid – 1.
Perform the same steps (if Kth number is not a multiple of A) for B and then for C.
Since the Kth number is bound to be a multiple of either A, B or C, these three Binary Search will definitely return the result.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define ll long long intusing 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// LCM of A and Bint lcm(int A, int B){ return (A * B) / gcd(A, B);}// Function to return the Kth element from// the required set if it a multiple of Aint checkA(int A, int B, int C, int K){ // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = A * mid; int divA = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans;}// Function to return the Kth element from// the required set if it a multiple of Bint checkB(int A, int B, int C, int K){ // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = B * mid; int divB = mid - 1; int divA = (value % A == 0) ? value / A - 1 : value / A; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans;}// Function to return the Kth element from// the required set if it a multiple of Cint checkC(int A, int B, int C, int K){ // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = C * mid; int divC = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divA = (value % A == 0) ? value / A - 1 : value / A; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans;}// Function to return the Kth element from// the set of multiples of A, B and Cint findKthMultiple(int A, int B, int C, int K){ // Apply binary search on the multiples of A int res = checkA(A, B, C, K); // If the required element is not a // multiple of A then the multiples // of B and C need to be checked if (res == -1) res = checkB(A, B, C, K); // If the required element is neither // a multiple of A nor a multiple // of B then the multiples of C // need to be checked if (res == -1) res = checkC(A, B, C, K); return res;}// Driver codeint main(){ int A = 2, B = 4, C = 5, K = 5; cout << findKthMultiple(A, B, C, K); return 0;} |
Java
// Java implementation of the above 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 // LCM of A and B static int lcm(int A, int B) { return (A * B) / gcd(A, B); } // Function to return the Kth element from // the required set if it a multiple of A static int checkA(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = A * mid; int divA = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of B static int checkB(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = B * mid; int divB = mid - 1; int divA = (value % A == 0) ? value / A - 1 : value / A; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of C static int checkC(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = C * mid; int divC = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divA = (value % A == 0) ? value / A - 1 : value / A; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the set of multiples of A, B and C static int findKthMultiple(int A, int B, int C, int K) { // Apply binary search on the multiples of A int res = checkA(A, B, C, K); // If the required element is not a // multiple of A then the multiples // of B and C need to be checked if (res == -1) res = checkB(A, B, C, K); // If the required element is neither // a multiple of A nor a multiple // of B then the multiples of C // need to be checked if (res == -1) res = checkC(A, B, C, K); return res; } // Driver code public static void main(String args[]) { int A = 2, B = 4, C = 5, K = 5; System.out.println(findKthMultiple(A, B, C, K)); } }// This code is contributed by AnkitRai01 |
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# LCM of A and Bdef lcm(A, B): return (A * B) // gcd(A, B)# Function to return the Kth element from# the required set if it a multiple of Adef checkA(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = A * mid divA = mid - 1 divB = value // B - 1 if (value % B == 0) \ else value // B divC = value // C - 1 if (value % C == 0) \ else value // C divAB = value // lcm(A, B) - 1 \ if (value % lcm(A, B) == 0) \ else value // lcm(A, B) divBC = value // lcm(C, B) - 1 \ if (value % lcm(C, B) == 0) \ else value // lcm(C, B) divAC = value // lcm(A, C) - 1 \ if (value % lcm(A, C) == 0) \ else value // lcm(A, C) divABC = value // lcm(A, lcm(B, C)) - 1 \ if (value % lcm(A, lcm(B, C)) == 0) \ else value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans# Function to return the Kth element from# the required set if it a multiple of Bdef checkB(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = B * mid divB = mid - 1 if (value % A == 0): divA = value // A - 1 else: value // A if (value % C == 0): divC = value // C - 1 else: value // C if (value % lcm(A, B) == 0): divAB = value // lcm(A, B) -1 else: value // lcm(A, B) if (value % lcm(C, B) == 0): divBC = value // lcm(C, B) -1 else: value // lcm(C, B) if (value % lcm(A, C) == 0): divAC = value // lcm(A, C) -1 else: value // lcm(A, C) if (value % lcm(A, lcm(B, C)) == 0): divABC = value // lcm(A, lcm(B, C)) - 1 else: value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans# Function to return the Kth element from# the required set if it a multiple of Cdef checkC(A, B, C, K): # Start and End for Binary Search start = 1 end = K # If no answer found return -1 ans = -1 while (start <= end): mid = (start + end) // 2 value = C * mid divC = mid - 1 if (value % B == 0): divB = value // B - 1 else: value // B if (value % A == 0): divA = value // A - 1 else: value // A if (value % lcm(A, B) == 0): divAB = value // lcm(A, B) -1 else: value // lcm(A, B) if (value % lcm(C, B) == 0): divBC = value // lcm(C, B) -1 else: value // lcm(C, B) if (value % lcm(A, C) == 0): divAC = value // lcm(A, C) -1 else: value // lcm(A, C) if (value % lcm(A, lcm(B, C)) == 0): divABC = value // lcm(A, lcm(B, C)) - 1 else: value // lcm(A, lcm(B, C)) # Inclusion and Exclusion elem = divA + divB + divC - \ divAC - divBC - divAB + divABC if (elem == (K - 1)): ans = value break # Multiple should be smaller elif (elem > (K - 1)): end = mid - 1 # Multiple should be bigger else : start = mid + 1 return ans# Function to return the Kth element from# the set of multiples of A, B and Cdef findKthMultiple(A, B, C, K): # Apply binary search on the multiples of A res = checkA(A, B, C, K) # If the required element is not a # multiple of A then the multiples # of B and C need to be checked if (res == -1): res = checkB(A, B, C, K) # If the required element is neither # a multiple of A nor a multiple # of B then the multiples of C # need to be checked if (res == -1): res = checkC(A, B, C, K) return res# Driver codeA = 2B = 4C = 5K = 5print(findKthMultiple(A, B, C, K))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the above 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 // LCM of A and B static int lcm(int A, int B) { return (A * B) / gcd(A, B); } // Function to return the Kth element from // the required set if it a multiple of A static int checkA(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = A * mid; int divA = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of B static int checkB(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = B * mid; int divB = mid - 1; int divA = (value % A == 0) ? value / A - 1 : value / A; int divC = (value % C == 0) ? value / C - 1 : value / C; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of C static int checkC(int A, int B, int C, int K) { // Start and End for Binary Search int start = 1; int end = K; // If no answer found return -1 int ans = -1; while (start <= end) { int mid = (start + end) / 2; int value = C * mid; int divC = mid - 1; int divB = (value % B == 0) ? value / B - 1 : value / B; int divA = (value % A == 0) ? value / A - 1 : value / A; int divAB = (value % lcm(A, B) == 0) ? value / lcm(A, B) - 1 : value / lcm(A, B); int divBC = (value % lcm(C, B) == 0) ? value / lcm(C, B) - 1 : value / lcm(C, B); int divAC = (value % lcm(A, C) == 0) ? value / lcm(A, C) - 1 : value / lcm(A, C); int divABC = (value % lcm(A, lcm(B, C)) == 0) ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)); // Inclusion and Exclusion int elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem == (K - 1)) { ans = value; break; } // Multiple should be smaller else if (elem > (K - 1)) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the set of multiples of A, B and C static int findKthMultiple(int A, int B, int C, int K) { // Apply binary search on the multiples of A int res = checkA(A, B, C, K); // If the required element is not a // multiple of A then the multiples // of B and C need to be checked if (res == -1) res = checkB(A, B, C, K); // If the required element is neither // a multiple of A nor a multiple // of B then the multiples of C // need to be checked if (res == -1) res = checkC(A, B, C, K); return res; } // Driver code public static void Main(String []args) { int A = 2, B = 4, C = 5, K = 5; Console.WriteLine(findKthMultiple(A, B, C, K)); } }// This code is contributed by Arnab Kundu |
Javascript
<script> // JavaScript implementation of the above 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 // LCM of A and B function lcm(A, B) { return (A * B) / gcd(A, B); } // Function to return the Kth element from // the required set if it a multiple of A function checkA(A, B, C, K) { // Start and End for Binary Search var start = 1; var end = K; // If no answer found return -1 var ans = -1; while (start <= end) { var mid = parseInt((start + end) / 2); var value = A * mid; var divA = mid - 1; var divB = parseInt(value % B === 0 ? value / B - 1 : value / B); var divC = parseInt(value % C === 0 ? value / C - 1 : value / C); var divAB = parseInt( value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B) ); var divBC = parseInt( value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B) ); var divAC = parseInt( value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C) ); var divABC = parseInt( value % lcm(A, lcm(B, C)) === 0 ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)) ); // Inclusion and Exclusion var elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem === K - 1) { ans = value; break; } // Multiple should be smaller else if (elem > K - 1) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of B function checkB(A, B, C, K) { // Start and End for Binary Search var start = 1; var end = K; // If no answer found return -1 var ans = -1; while (start <= end) { var mid = parseInt((start + end) / 2); var value = B * mid; var divB = mid - 1; var divA = parseInt(value % A === 0 ? value / A - 1 : value / A); var divC = parseInt(value % C === 0 ? value / C - 1 : value / C); var divAB = parseInt( value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B) ); var divBC = parseInt( value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B) ); var divAC = parseInt( value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C) ); var divABC = parseInt( value % lcm(A, lcm(B, C)) === 0 ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)) ); // Inclusion and Exclusion var elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem === K - 1) { ans = value; break; } // Multiple should be smaller else if (elem > K - 1) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the required set if it a multiple of C function checkC(A, B, C, K) { // Start and End for Binary Search var start = 1; var end = K; // If no answer found return -1 var ans = -1; while (start <= end) { var mid = parseInt((start + end) / 2); var value = C * mid; var divC = mid - 1; var divB = parseInt(value % B === 0 ? value / B - 1 : value / B); var divA = parseInt(value % A === 0 ? value / A - 1 : value / A); var divAB = parseInt( value % lcm(A, B) === 0 ? value / lcm(A, B) - 1 : value / lcm(A, B) ); var divBC = parseInt( value % lcm(C, B) === 0 ? value / lcm(C, B) - 1 : value / lcm(C, B) ); var divAC = parseInt( value % lcm(A, C) === 0 ? value / lcm(A, C) - 1 : value / lcm(A, C) ); var divABC = parseInt( value % lcm(A, lcm(B, C)) === 0 ? value / lcm(A, lcm(B, C)) - 1 : value / lcm(A, lcm(B, C)) ); // Inclusion and Exclusion var elem = divA + divB + divC - divAC - divBC - divAB + divABC; if (elem === K - 1) { ans = value; break; } // Multiple should be smaller else if (elem > K - 1) { end = mid - 1; } // Multiple should be bigger else { start = mid + 1; } } return ans; } // Function to return the Kth element from // the set of multiples of A, B and C function findKthMultiple(A, B, C, K) { // Apply binary search on the multiples of A var res = checkA(A, B, C, K); console.log(res); // If the required element is not a // multiple of A then the multiples // of B and C need to be checked if (res === -1) res = checkB(A, B, C, K); // If the required element is neither // a multiple of A nor a multiple // of B then the multiples of C // need to be checked if (res === -1) res = checkC(A, B, C, K); return res; } // Driver code var A = 2, B = 4, C = 5, K = 5; document.write(findKthMultiple(A, B, C, K)); // This code is contributed by rdtank. </script> |
8
Time Complexity: O(log K * log(min(a, b))), where a and b are parameters of gcd
Auxiliary Space: O(log(min(a, b)))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!



