Minimum length of subsequence having unit GCD | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findPrimeFactors ( int n ) { vector < int > primeFactors ( 9 , 0 ) ; 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 ; vector < int > PrimeFactors ( j ) ; for ( int i = 0 ; i < j ; i ++ ) { PrimeFactors [ i ] = primeFactors [ i ] ; } return PrimeFactors ; } void findShortestSubsequence ( vector < int > & dp , vector < int > a , int index , vector < int > primeFactors ) { int n = a . size ( ) ; for ( int j = index ; j < n ; j ++ ) { int bitmask = 0 ; for ( int p = 0 ; p < primeFactors . size ( ) ; p ++ ) { if ( ( a [ j ] % primeFactors [ p ] ) == 0 ) { bitmask ^= ( 1 << p ) ; } } for ( int i = 0 ; i < dp . size ( ) ; i ++ ) { if ( dp [ i ] == n + 1 ) continue ; dp [ bitmask & i ] = min ( dp [ bitmask & i ] , dp [ i ] + 1 ) ; } } } void printMinimumLength ( vector < int > a ) { int Min = a . size ( ) + 1 ; for ( int i = 0 ; i < a . size ( ) - 1 ; i ++ ) { vector < int > primeFactors = findPrimeFactors ( a [ i ] ) ; int n = primeFactors . size ( ) ; vector < int > dp ( 1 << n , a . size ( ) + 1 ) ; int setBits = ( 1 << n ) - 1 ; dp [ setBits ] = 1 ; findShortestSubsequence ( dp , a , i + 1 , primeFactors ) ; Min = min ( dp [ 0 ] , Min ) ; } if ( Min == ( a . size ( ) + 1 ) ) cout << -1 << endl ; else cout << Min << endl ; } int main ( ) { vector < int > arr = { 2 , 6 , 12 , 3 } ; printMinimumLength ( arr ) ; return 0 ; }