Problem: Smallest Sub-Array

Given an integer G and an array A[ ], find the length of the minimum sub-array whose Greatest Common Divisor equals to G.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer G, where G is the required Greatest Common Divisor. The second line of each test case contains an integer N, where N is the size of the array A[ ]. The third line of each test case contains N space separated integers denoting elements of the array A[ ].

Output:
Print out the length of the smallest sub-array with GCD = G. If there is no such sub-array formed, then print “-1”.

Constraints:
1 <= T <= 100
1 < N <= 30
0<= A[i]<=100
1 < G <= 100

Examples :

Input:

3
3
8
6 9 12 10 15 24 36 27
4
7
21 3 12 4 32 7 5
2
6
9 12 15 24 36 27

Output :
2
2
-1

Implementation: Python 2.7

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def subarrays(l):
    """
    return all subarrays of l 
    subarray having length >= 2
    """
    res, length = [], 2
    while length < len(l):
        for i in range(0, len(l)):
            if i + length <= len(l):
                res.append(l[i:i+length])
        length += 1
    return res

def gcd_array(l):
    _gcd = l[0]
    for i in range(1, len(l)):
        _gcd = gcd(_gcd, l[i])
    return _gcd

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        g, n = input(), input()
        l = map(int, raw_input().split())
        sub_arrs = subarrays(l)
        for sa in sub_arrs:
            if gcd_array(sa) == g:
                print len(sa)
                break
        else:
            print -1

 

Advertisements