Kth number from the set of multiples of numbers A , B and C | Function to return the GCD of A and B ; Function to return the LCM of A and B ; Function to return the Kth element from the required set if it a multiple of A ; Start and End for Binary Search ; If no answer found return - 1 ; Inclusion and Exclusion ; Multiple should be smaller ; Multiple should be bigger ; Function to return the Kth element from the required set if it a multiple of B ; Start and End for Binary Search ; If no answer found return - 1 ; Inclusion and Exclusion ; Multiple should be smaller ; Multiple should be bigger ; Function to return the Kth element from the required set if it a multiple of C ; Start and End for Binary Search ; If no answer found return - 1 ; Inclusion and Exclusion ; Multiple should be smaller ; Multiple should be bigger ; Function to return the Kth element from the set of multiples of A , B and C ; Apply binary search on the multiples of A ; If the required element is not a multiple of A then the multiples of B and C need to be checked ; If the required element is neither a multiple of A nor a multiple of B then the multiples of C need to be checked ; Driver code
def gcd ( A , B ) : NEW_LINE INDENT if ( B == 0 ) : NEW_LINE INDENT return A NEW_LINE DEDENT return gcd ( B , A % B ) NEW_LINE DEDENT def lcm ( A , B ) : NEW_LINE INDENT return ( A * B ) // gcd ( A , B ) NEW_LINE DEDENT def checkA ( A , B , C , K ) : NEW_LINE INDENT start = 1 NEW_LINE end = K NEW_LINE ans = - 1 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE value = A * mid NEW_LINE divA = mid - 1 NEW_LINE divB = value // B - 1 if ( value % B == 0 ) else value // B NEW_LINE divC = value // C - 1 if ( value % C == 0 ) else value // C NEW_LINE divAB = value // lcm ( A , B ) - 1 if ( value % lcm ( A , B ) == 0 ) else value // lcm ( A , B ) NEW_LINE divBC = value // lcm ( C , B ) - 1 if ( value % lcm ( C , B ) == 0 ) else value // lcm ( C , B ) NEW_LINE divAC = value // lcm ( A , C ) - 1 if ( value % lcm ( A , C ) == 0 ) else value // lcm ( A , C ) NEW_LINE divABC = value // lcm ( A , lcm ( B , C ) ) - 1 if ( value % lcm ( A , lcm ( B , C ) ) == 0 ) else value // lcm ( A , lcm ( B , C ) ) NEW_LINE elem = divA + divB + divC - divAC - divBC - divAB + divABC NEW_LINE if ( elem == ( K - 1 ) ) : NEW_LINE INDENT ans = value NEW_LINE break NEW_LINE DEDENT elif ( elem > ( K - 1 ) ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def checkB ( A , B , C , K ) : NEW_LINE INDENT start = 1 NEW_LINE end = K NEW_LINE ans = - 1 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE value = B * mid NEW_LINE divB = mid - 1 NEW_LINE if ( value % A == 0 ) : NEW_LINE INDENT divA = value // A - 1 NEW_LINE DEDENT else : value // A NEW_LINE if ( value % C == 0 ) : NEW_LINE INDENT divC = value // C - 1 NEW_LINE DEDENT else : value // C NEW_LINE if ( value % lcm ( A , B ) == 0 ) : NEW_LINE INDENT divAB = value // lcm ( A , B ) - 1 NEW_LINE DEDENT else : value // lcm ( A , B ) NEW_LINE if ( value % lcm ( C , B ) == 0 ) : NEW_LINE INDENT divBC = value // lcm ( C , B ) - 1 NEW_LINE DEDENT else : value // lcm ( C , B ) NEW_LINE if ( value % lcm ( A , C ) == 0 ) : NEW_LINE INDENT divAC = value // lcm ( A , C ) - 1 NEW_LINE DEDENT else : value // lcm ( A , C ) NEW_LINE if ( value % lcm ( A , lcm ( B , C ) ) == 0 ) : NEW_LINE INDENT divABC = value // lcm ( A , lcm ( B , C ) ) - 1 NEW_LINE DEDENT else : value // lcm ( A , lcm ( B , C ) ) NEW_LINE elem = divA + divB + divC - divAC - divBC - divAB + divABC NEW_LINE if ( elem == ( K - 1 ) ) : NEW_LINE INDENT ans = value NEW_LINE break NEW_LINE DEDENT elif ( elem > ( K - 1 ) ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def checkC ( A , B , C , K ) : NEW_LINE INDENT start = 1 NEW_LINE end = K NEW_LINE ans = - 1 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE value = C * mid NEW_LINE divC = mid - 1 NEW_LINE if ( value % B == 0 ) : NEW_LINE INDENT divB = value // B - 1 NEW_LINE DEDENT else : value // B NEW_LINE if ( value % A == 0 ) : NEW_LINE INDENT divA = value // A - 1 NEW_LINE DEDENT else : value // A NEW_LINE if ( value % lcm ( A , B ) == 0 ) : NEW_LINE INDENT divAB = value // lcm ( A , B ) - 1 NEW_LINE DEDENT else : value // lcm ( A , B ) NEW_LINE if ( value % lcm ( C , B ) == 0 ) : NEW_LINE INDENT divBC = value // lcm ( C , B ) - 1 NEW_LINE DEDENT else : value // lcm ( C , B ) NEW_LINE if ( value % lcm ( A , C ) == 0 ) : NEW_LINE INDENT divAC = value // lcm ( A , C ) - 1 NEW_LINE DEDENT else : value // lcm ( A , C ) NEW_LINE if ( value % lcm ( A , lcm ( B , C ) ) == 0 ) : NEW_LINE INDENT divABC = value // lcm ( A , lcm ( B , C ) ) - 1 NEW_LINE DEDENT else : value // lcm ( A , lcm ( B , C ) ) NEW_LINE elem = divA + divB + divC - divAC - divBC - divAB + divABC NEW_LINE if ( elem == ( K - 1 ) ) : NEW_LINE INDENT ans = value NEW_LINE break NEW_LINE DEDENT elif ( elem > ( K - 1 ) ) : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def findKthMultiple ( A , B , C , K ) : NEW_LINE INDENT res = checkA ( A , B , C , K ) NEW_LINE if ( res == - 1 ) : NEW_LINE INDENT res = checkB ( A , B , C , K ) NEW_LINE DEDENT if ( res == - 1 ) : NEW_LINE INDENT res = checkC ( A , B , C , K ) NEW_LINE DEDENT return res NEW_LINE DEDENT A = 2 NEW_LINE B = 4 NEW_LINE C = 5 NEW_LINE K = 5 NEW_LINE print ( findKthMultiple ( A , B , C , K ) ) NEW_LINE