Smallest subarray with GCD as 1 | Segment Tree | C ++ implementation of the approach ; Array to store segment - tree ; Function to build segment - tree to answer range GCD queries ; Base - case ; Mid element of the range ; Merging the result of left and right sub - tree ; Function to perform range GCD queries ; Base - cases ; Mid - element ; Calling left and right child ; Function to find the required length ; Building the segment tree ; Two pointer variables ; To store the final answer ; Looping ; Incrementing j till we don 't get  a gcd value of 1 ; Updating the final answer ; Incrementing i ; Updating j ; Returning the final answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxLen  30 NEW_LINE int seg [ 3 * maxLen ] ; int build ( int l , int r , int in , int * arr ) { if ( l == r ) return seg [ in ] = arr [ l ] ; int mid = ( l + r ) / 2 ; return seg [ in ] = __gcd ( build ( l , mid , 2 * in + 1 , arr ) , build ( mid + 1 , r , 2 * in + 2 , arr ) ) ; } int query ( int l , int r , int l1 , int r1 , int in ) { if ( l1 <= l and r <= r1 ) return seg [ in ] ; if ( l > r1 or r < l1 ) return 0 ; int mid = ( l + r ) / 2 ; return __gcd ( query ( l , mid , l1 , r1 , 2 * in + 1 ) , query ( mid + 1 , r , l1 , r1 , 2 * in + 2 ) ) ; } int findLen ( int * arr , int n ) { build ( 0 , n - 1 , 0 , arr ) ; int i = 0 , j = 0 ; int ans = INT_MAX ; while ( i < n ) { while ( j < n and query ( 0 , n - 1 , i , j , 0 ) != 1 ) j ++ ; if ( j == n ) break ; ans = min ( ( j - i + 1 ) , ans ) ; i ++ ; j = max ( j , i ) ; } if ( ans == INT_MAX ) return -1 ; else return ans ; } int main ( ) { int arr [ ] = { 2 , 2 , 2 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << findLen ( arr , n ) ; return 0 ; }