Smallest subarray with GCD as 1 | Segment Tree | Javascript 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
let maxLen = 30 ; let seg = new Array ( 3 * maxLen ) ; function build ( l , r , In , arr ) { if ( l == r ) return seg [ In ] = arr [ l ] ; let mid = Math . floor ( ( l + r ) / 2 ) ; return seg [ In ] = __gcd ( build ( l , mid , 2 * In + 1 , arr ) , build ( mid + 1 , r , 2 * In + 2 , arr ) ) ; } function query ( l , r , l1 , r1 , In ) { if ( l1 <= l && r <= r1 ) return seg [ In ] ; if ( l > r1 r < l1 ) return 0 ; let mid = Math . floor ( ( l + r ) / 2 ) ; return __gcd ( query ( l , mid , l1 , r1 , 2 * In + 1 ) , query ( mid + 1 , r , l1 , r1 , 2 * In + 2 ) ) ; } function findLen ( arr , n ) { build ( 0 , n - 1 , 0 , arr ) ; let i = 0 , j = 0 ; let ans = Number . MAX_VALUE ; 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 == Number . MAX_VALUE ) return - 1 ; else return ans ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } let arr = [ 2 , 2 , 2 ] ; let n = arr . length ; document . write ( findLen ( arr , n ) ) ;