**Problem Link :** https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-enemy-daddu-ji-2

**Required Knowledge :** Segment Tree(https://en.wikipedia.org/wiki/Segment_tree), Binary Search(https://en.wikipedia.org/wiki/Binary_search_algorithm).

**Explanation : **

You are given n numbers and an integer k, you are asked to find the length of minimum sub-array whose gcd is k. If any number is k then the answer should be 1 as that sub-array will have gcd k and length 1 which is the minimum. Now what to do if no number is equal to k. We need to find all the sub-arrays whose gcd is k. Let us now declare a minimum variable whose value is more than n. Now start with index 1, we will now find the gcd of sub-array 1 to (n/2)index using segment tree. If gcd is = k we, we store the minimum of the length of the found sub-array and the original value of minimum in minimum. minimum = min(minimum, length of found sub-array). If gcd is greater than k then we will get the sub-array with gcd k further as moving back will give gcd more than k. So now binary search b/w n/2 and n. Similarly if gcd is less than k, we will either get gcd k b/w index 1 and n/2 or we will not get any sub-array with gcd k. So now finding gcd of a sub-array will have time complexity of O(logn) and binary search will also happen in log(n). Therefore for each index total complexity of O(logn*logn). Since there are n index we need to find for all, therefore the required complexity of the solution is O(n*(logn)^2).

Now if value of minimum is equal to the assigned value in the beginning, print -1 else print minimum.

**Some useful links on segment tree :**

http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://www.cse.iitk.ac.in/users/aca/lop12/slides/06.pdf

https://proclubdaiict.wordpress.com/2015/01/25/segment-trees/

**Setter’s Solution :** http://ideone.com/wqVgEI

For any doubts you can contact me at 201301151@daiict.ac.in or message me on Facebook (https://www.facebook.com/nikhil.tekwani.18).