Smallest perfect Cube divisible by all elements of an array | Function to return the gcd of two numbers ; Function to return the lcm of all the elements of the array ; To calculate lcm of two numbers multiply them and divide the result by gcd of both the numbers ; Return the LCM of the array elements ; Function to return the smallest perfect cube divisible by all the elements of arr [ ] ; LCM of all the elements of arr [ ] ; If 2 divides lcm cnt number of times ; Check all the numbers that divide lcm ; Return the answer ; Driver code
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def lcmOfArray ( arr , n ) : NEW_LINE INDENT if ( n < 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT lcm = arr [ 0 ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT lcm = ( lcm * arr [ i ] ) // gcd ( lcm , arr [ i ] ) ; NEW_LINE DEDENT return lcm NEW_LINE DEDENT def minPerfectCube ( arr , n ) : NEW_LINE INDENT lcm = lcmOfArray ( arr , n ) NEW_LINE minPerfectCube = lcm NEW_LINE cnt = 0 NEW_LINE while ( lcm > 1 and lcm % 2 == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE lcm //= 2 NEW_LINE DEDENT if ( cnt % 3 == 2 ) : NEW_LINE INDENT minPerfectCube *= 2 NEW_LINE DEDENT elif ( cnt % 3 == 1 ) : NEW_LINE INDENT minPerfectCube *= 4 NEW_LINE DEDENT i = 3 NEW_LINE while ( lcm > 1 ) : NEW_LINE INDENT cnt = 0 NEW_LINE while ( lcm % i == 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE lcm //= i NEW_LINE DEDENT if ( cnt % 3 == 1 ) : NEW_LINE INDENT minPerfectCube *= i * i NEW_LINE DEDENT elif ( cnt % 3 == 2 ) : NEW_LINE INDENT minPerfectCube *= i NEW_LINE DEDENT i += 2 NEW_LINE DEDENT return minPerfectCube NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 10 , 125 , 14 , 42 , 100 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minPerfectCube ( arr , n ) ) NEW_LINE DEDENT