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 int using namespace std; // Function to return the // GCD of A and B 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 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 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 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 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 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 int 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 B def gcd(A, B): if (B = = 0 ): return A return gcd(B, A % B) # Function to return the # LCM of A and B def 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 def 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 B def 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 C def 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 C def 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 code A = 2 B = 4 C = 5 K = 5 print (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 neveropen!