Smallest subarray with GCD as 1 | Segment Tree | Python3 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 ; Buildinng the segment tree ; Two pointer variables ; To store the final answer ; Loopinng ; 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
from math import gcd as __gcd NEW_LINE maxLen = 30 NEW_LINE seg = [ 0 for i in range ( 3 * maxLen ) ] NEW_LINE def build ( l , r , inn , arr ) : NEW_LINE INDENT if ( l == r ) : NEW_LINE INDENT seg [ inn ] = arr [ l ] NEW_LINE return seg [ inn ] NEW_LINE DEDENT mid = ( l + r ) // 2 NEW_LINE seg [ inn ] = __gcd ( build ( l , mid , 2 * inn + 1 , arr ) , build ( mid + 1 , r , 2 * inn + 2 , arr ) ) NEW_LINE return seg [ inn ] NEW_LINE DEDENT def query ( l , r , l1 , r1 , inn ) : NEW_LINE INDENT if ( l1 <= l and r <= r1 ) : NEW_LINE INDENT return seg [ inn ] NEW_LINE DEDENT if ( l > r1 or r < l1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT mid = ( l + r ) // 2 NEW_LINE x = __gcd ( query ( l , mid , l1 , r1 , 2 * inn + 1 ) , query ( mid + 1 , r , l1 , r1 , 2 * inn + 2 ) ) NEW_LINE return x NEW_LINE DEDENT def findLen ( arr , n ) : NEW_LINE INDENT build ( 0 , n - 1 , 0 , arr ) NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE ans = 10 ** 9 NEW_LINE while ( i < n ) : NEW_LINE INDENT while ( j < n and query ( 0 , n - 1 , i , j , 0 ) != 1 ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT if ( j == n ) : NEW_LINE INDENT break ; NEW_LINE DEDENT ans = minn ( ( j - i + 1 ) , ans ) NEW_LINE i += 1 NEW_LINE j = max ( j , i ) NEW_LINE DEDENT if ( ans == 10 ** 9 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return ans NEW_LINE DEDENT DEDENT arr = [ 2 , 2 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findLen ( arr , n ) ) NEW_LINE