Sunday, November 17, 2024
Google search engine
HomeData Modelling & AIKth number from the set of multiples of numbers A, B and...

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:
The required set is {1, 2, 3, 4, 5, …}
Input: A = 2, B = 4, C = 5, K = 5 
Output:
 

 

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>


Output: 

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)))

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!

RELATED ARTICLES

Most Popular

Recent Comments