Minimum length of subsequence having unit GCD | Function that finds the prime factors of a number ; To store the prime factor ; 2 s that divide n ; N must be odd at this point Skip one element ; Update the prime factor ; If n is a prime number greater than 2 ; Function that finds the shortest subsequence ; Check if the prime factor of first number , is also the prime factor of the rest numbers in array ; Set corresponding bit of prime factor to 1 , it means both these numbers have the same prime factor ; If no states encountered so far continue for this combination of bits ; Update this state with minimum ways to reach this state ; Function that print the minimum length of subsequence ; Find the prime factors of the first number ; Initialize the array with maximum steps , size of the array + 1 for instance ; Total number of set bits is equal to the total number of prime factors ; Indicates there is one way to reach the number under consideration ; State 0 corresponds to gcd of 1 ; If not found such subsequence then print " - 1" ; Else print the length ; Driver Code ; Given array arr [ ] ; Function Call
def findPrimeFactors ( n ) : NEW_LINE INDENT primeFactors = [ 0 for i in range ( 9 ) ] NEW_LINE j = 0 NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT primeFactors [ j ] = 2 NEW_LINE j += 1 NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT n >>= 1 NEW_LINE DEDENT DEDENT i = 3 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT primeFactors [ j ] = i NEW_LINE j += 1 NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT n //= i NEW_LINE DEDENT DEDENT i += 2 NEW_LINE DEDENT if ( n > 2 ) : NEW_LINE INDENT primeFactors [ j ] = n NEW_LINE j += 1 NEW_LINE DEDENT for i in range ( 0 , j + 1 ) : NEW_LINE INDENT primeFactors [ i ] = 0 NEW_LINE DEDENT return primeFactors NEW_LINE DEDENT def findShortestSubsequence ( dp , a , index , primeFactors ) : NEW_LINE INDENT n = len ( a ) NEW_LINE for j in range ( index , n ) : NEW_LINE INDENT bitmask = 0 NEW_LINE for p in range ( len ( primeFactors ) ) : NEW_LINE INDENT if ( primeFactors [ p ] != 0 and a [ j ] % primeFactors [ p ] == 0 ) : NEW_LINE INDENT bitmask ^= ( 1 << p ) NEW_LINE DEDENT DEDENT for i in range ( len ( dp ) ) : NEW_LINE INDENT if ( dp [ i ] == n + 1 ) : NEW_LINE INDENT continue NEW_LINE DEDENT dp [ bitmask & i ] = min ( dp [ bitmask & i ] , dp [ i ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT def printMinimumLength ( a ) : NEW_LINE INDENT mn = len ( a ) + 1 NEW_LINE for i in range ( len ( a ) - 1 ) : NEW_LINE INDENT primeFactors = findPrimeFactors ( a [ i ] ) NEW_LINE n = len ( primeFactors ) NEW_LINE dp = [ 0 for i in range ( 1 << n ) ] NEW_LINE dp = [ len ( a ) + 1 for i in range ( len ( dp ) ) ] NEW_LINE setBits = ( 1 << n ) - 1 NEW_LINE dp [ setBits ] = 1 NEW_LINE findShortestSubsequence ( dp , a , i + 1 , primeFactors ) NEW_LINE mn = min ( dp [ 0 ] , mn ) NEW_LINE DEDENT if ( mn == len ( a ) + 1 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( mn ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 6 , 12 , 3 ] NEW_LINE printMinimumLength ( arr ) NEW_LINE DEDENT