text: 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
code: function gcd ( A , B ) { if ( B === 0 ) return A ; return gcd ( B , A % B ) ; } function lcm ( A , B ) { return ( A * B ) / gcd ( A , B ) ; } function checkA ( A , B , C , K ) { var start = 1 ; var end = K ; 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 ) ) ) ; var elem = divA + divB + divC - divAC - divBC - divAB + divABC ; if ( elem === K - 1 ) { ans = value ; break ; } else if ( elem > K - 1 ) { end = mid - 1 ; } else { start = mid + 1 ; } } return ans ; } function checkB ( A , B , C , K ) { var start = 1 ; var end = K ; 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 ) ) ) ; var elem = divA + divB + divC - divAC - divBC - divAB + divABC ; if ( elem === K - 1 ) { ans = value ; break ; } else if ( elem > K - 1 ) { end = mid - 1 ; } else { start = mid + 1 ; } } return ans ; } function checkC ( A , B , C , K ) { var start = 1 ; var end = K ; 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 ) ) ) ; var elem = divA + divB + divC - divAC - divBC - divAB + divABC ; if ( elem === K - 1 ) { ans = value ; break ; } else if ( elem > K - 1 ) { end = mid - 1 ; } else { start = mid + 1 ; } } return ans ; } function findKthMultiple ( A , B , C , K ) { var res = checkA ( A , B , C , K ) ; console . log ( res ) ; if ( res === - 1 ) res = checkB ( A , B , C , K ) ; if ( res === - 1 ) res = checkC ( A , B , C , K ) ; return res ; } var A = 2 , B = 4 , C = 5 , K = 5 ; document . write ( findKthMultiple ( A , B , C , K ) ) ;