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 ; Given array arr [ ] ; Function Call
function findPrimeFactors ( n ) { let primeFactors = new Array ( 9 ) . fill ( 0 ) ; let j = 0 ; if ( n % 2 == 0 ) { primeFactors [ j ++ ] = 2 ; while ( n % 2 == 0 ) n >>= 1 ; } for ( let i = 3 ; i * i <= n ; i += 2 ) { if ( n % i == 0 ) { primeFactors [ j ++ ] = i ; while ( n % i == 0 ) n /= i ; } } if ( n > 2 ) primeFactors [ j ++ ] = n ; let PrimeFactors = new Array ( j ) ; for ( let i = 0 ; i < j ; i ++ ) { PrimeFactors [ i ] = primeFactors [ i ] ; } return PrimeFactors ; } function findShortestSubsequence ( dp , a , index , primeFactors ) { let n = a . length ; for ( let j = index ; j < n ; j ++ ) { let bitmask = 0 ; for ( let p = 0 ; p < primeFactors . length ; p ++ ) { if ( ( a [ j ] % primeFactors [ p ] ) == 0 ) { bitmask ^= ( 1 << p ) ; } } for ( let i = 0 ; i < dp . length ; i ++ ) { if ( dp [ i ] == n + 1 ) continue ; dp [ bitmask & i ] = Math . min ( dp [ bitmask & i ] , dp [ i ] + 1 ) ; } } } function prletMinimumLength ( a ) { let Min = a . length + 1 ; for ( let i = 0 ; i < a . length - 1 ; i ++ ) { let primeFactors = findPrimeFactors ( a [ i ] ) ; let n = primeFactors . length ; let dp = new Array ( 1 << n ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = a . length + 1 } let setBits = ( 1 << n ) - 1 ; dp [ setBits ] = 1 ; findShortestSubsequence ( dp , a , i + 1 , primeFactors ) ; Min = Math . min ( dp [ 0 ] , Min ) ; } if ( Min == ( a . length + 1 ) ) document . write ( - 1 + " " ) ; else document . write ( Min + " " ) ; } let arr = [ 2 , 6 , 12 , 3 ] ; prletMinimumLength ( arr ) ;