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
using System ; class GFG { static int maxLen = 30 ; static int [ ] seg = new int [ 3 * maxLen ] ; static int build ( int l , int r , int ind , int [ ] arr ) { if ( l == r ) return seg [ ind ] = arr [ l ] ; int mid = ( l + r ) / 2 ; return seg [ ind ] = __gcd ( build ( l , mid , 2 * ind + 1 , arr ) , build ( mid + 1 , r , 2 * ind + 2 , arr ) ) ; } static int query ( int l , int r , int l1 , int r1 , int ind ) { if ( l1 <= l && r <= r1 ) return seg [ ind ] ; if ( l > r1 r < l1 ) return 0 ; int mid = ( l + r ) / 2 ; return __gcd ( query ( l , mid , l1 , r1 , 2 * ind + 1 ) , query ( mid + 1 , r , l1 , r1 , 2 * ind + 2 ) ) ; } static int findLen ( int [ ] arr , int n ) { build ( 0 , n - 1 , 0 , arr ) ; int i = 0 , j = 0 ; int ans = int . MaxValue ; while ( i < n ) { while ( j < n && query ( 0 , n - 1 , i , j , 0 ) != 1 ) j ++ ; if ( j == n ) break ; ans = Math . Min ( ( j - i + 1 ) , ans ) ; i ++ ; j = Math . Max ( j , i ) ; } if ( ans == int . MaxValue ) return - 1 ; else return ans ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void Main ( ) { int [ ] arr = { 2 , 2 , 2 } ; int n = arr . Length ; Console . WriteLine ( findLen ( arr , n ) ) ; } }