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

见题面

见题面