Minimum length of subsequence having unit GCD | Java program for the above approach ; 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
import java . io . * ; import java . util . * ; class GFG { private static int [ ] findPrimeFactors ( int n ) { int [ ] primeFactors = new int [ 9 ] ; int j = 0 ; if ( n % 2 == 0 ) { primeFactors [ j ++ ] = 2 ; while ( n % 2 == 0 ) n >>= 1 ; } for ( int 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 ; return Arrays . copyOfRange ( primeFactors , 0 , j ) ; } private static void findShortestSubsequence ( int [ ] dp , int [ ] a , int index , int [ ] primeFactors ) { int n = a . length ; for ( int j = index ; j < n ; j ++ ) { int bitmask = 0 ; for ( int p = 0 ; p < primeFactors . length ; p ++ ) { if ( a [ j ] % primeFactors [ p ] == 0 ) { bitmask ^= ( 1 << p ) ; } } for ( int i = 0 ; i < dp . length ; i ++ ) { if ( dp [ i ] == n + 1 ) continue ; dp [ bitmask & i ] = Math . min ( dp [ bitmask & i ] , dp [ i ] + 1 ) ; } } } private static void printMinimumLength ( int [ ] a ) { int min = a . length + 1 ; for ( int i = 0 ; i < a . length - 1 ; i ++ ) { int [ ] primeFactors = findPrimeFactors ( a [ i ] ) ; int n = primeFactors . length ; int [ ] dp = new int [ 1 << n ] ; Arrays . fill ( dp , a . length + 1 ) ; int setBits = ( 1 << n ) - 1 ; dp [ setBits ] = 1 ; findShortestSubsequence ( dp , a , i + 1 , primeFactors ) ; min = Math . min ( dp [ 0 ] , min ) ; } if ( min == a . length + 1 ) System . out . println ( - 1 ) ; else System . out . println ( min ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 6 , 12 , 3 } ; printMinimumLength ( arr ) ; } }