Given an integer G and an array arr[] of size N, find the length of the minimum subarray whose Greatest Common Divisor equals to G.
Example 1:
Input:
N = 8
arr[] = {6, 9, 7, 10, 12, 24, 36, 27}
G = 3
Output: 2
Explanation: GCD of subarray {6,9} is 3.
GCD of subarray {24, 36, 27} is also 3,
but {6, 9} is the smallest.
Example 2:
Input:
N = 6
Arr[] = {9, 12, 15, 24, 36, 27}
G = 2
Output: -1
Explanation: GCD 2 is not possible from 
any subarray from the given array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findSmallestSubArr() which takes arr[], n and g as input parameters and returns length of minimum subarray. Return -1 if no such subarray is possible.
Expected Time Complexity: O(N * (logN)^{2})
Expected Auxiliary Space: O(N * logN) 
Constraints:
1 <= N <= 10^{4}
1 <= arr[i] <= 10^{5}
1 <= G <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3

class Solution:
    def findSmallestSubArr(self, arr, n, g):
        # code here

Solutions:
import math, sys

class SegmentTree:

	def __init__(self, nums, n):
		self.nums = nums
		self.segTree = [0] * (2 * n)
		self.n = n

	def construct_segTree(self):
		n = self.n
		for i in range(n):
			self.segTree[n + i] = self.nums[i]
		for i in range(n - 1, 0, -1):
			self.segTree[i] = math.gcd(self.segTree[i << 1], self.segTree[i << 1 | 1])

	def update(self, pos, val):
		n = self.n
		self.segTree[pos + n] = val
		pos += n
		i = pos
		while i > 1:
			self.segTree[i >> 1] = math.gcd(self.segTree[i], self.segTree[i ^ 1])
			i >>= 1

	def rangeGcdQuery(self, low, high):
		low += n
		high += n
		ans = -1
		while low < high:
			if low & 1:
				if ans == -1:
					ans = self.segTree[low]
				ans = math.gcd(ans, self.segTree[low])
				low += 1
			if high & 1:
				high -= 1
				if ans == -1:
					ans = self.segTree[high]
				ans = math.gcd(ans, self.segTree[high])
			low >>= 1
			high >>= 1
		return ans

class Solution:

	def findSmallestSubArr(self, nums, n, g):
		segT = SegmentTree(nums, n)
		segT.construct_segTree()
		res = 100000007
		for i in range(n):
			if nums[i] % g:
				continue
			low = i
			high = n - 1
			temp = -1
			while low <= high:
				mid = (low + high) // 2
				gcd = segT.rangeGcdQuery(i, mid + 1)
				if gcd > g:
					low = mid + 1
				elif gcd < g:
					high = mid - 1
				else:
					temp = mid
					high = mid - 1
			if temp != -1:
				res = min(res, temp - i + 1)
		return -1 if res == 100000007 else res


from math import gcd, inf

class Solution:

	def findSmallestSubArr(self, x, n, g):
		dp = [0 for i in range(140000)]

		def f(i, j, kk=0):
			if i > j:
				return
			g = x[i]
			for k in range(i + 1, j + 1):
				g = gcd(x[k], g)
			dp[kk] = g
			if i == j:
				return
			f(i, (i + j) // 2, 2 * kk + 1)
			f((i + j) // 2 + 1, j, 2 * kk + 2)

		def query(i, j, ii, jj, kk=0):
			if j < ii or jj < i:
				return -1
			if ii <= i and j <= jj:
				return dp[kk]
			a = query(i, (i + j) // 2, ii, jj, 2 * kk + 1)
			b = query((i + j) // 2 + 1, j, ii, jj, 2 * kk + 2)
			if a == -1:
				return b
			if b == -1:
				return a
			return gcd(a, b)
		f(0, n - 1)
		ans = inf
		for ii in range(n):
			i = ii
			j = min(n - 1, ii + ans - 1)
			while i <= j:
				m = (i + j) // 2
				a = query(0, n - 1, ii, m)
				if a == g:
					ans = min(ans, m - ii + 1)
				if a <= g:
					j = m - 1
				else:
					i = m + 1
		return ans if ans != inf else -1