Last Updated: 16 Jun, 2021

Split array and GCD

Hard

Asked in company

Solve now

Problem statement

Ninja is learning GCD and he is playing with few numbers. Now he is being provided few numbers in an array. Now he is being asked to split the array such that in all the subarrays the GCD of the starting and the ending element is greater than 1. As this procedure is expensive so Ninja needs to create the minimum number of subarrays that satisfy the above property. If it is not possible to create such subarrays then return -1.

For eg:

Let arr[] = [2, 2, 4, 3, 6]. So minimum number of subarrays required is 2 which is [2, 2, 4] and [3, 6].

Input Format:

The first line of input contains a single integer ‘T’, denoting the number of test cases.

The second line of each test case contains ‘N’, denoting the number of elements in the array.

The third line of each test case contains the array elements.

Output Format :

The first and only line of each test case contains an integer denoting the minimum number of subarrays.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10    
1 <= N <= 10^4
0 <= arr[i] <= 10^5   

Time limit: 1 sec

Solve now

Approaches

01 Approach

We are traversing over all possible subarrays and checking if the given conditions are satisfied.

If conditions in all the subarrays are satisfied and the number of subarrays created is minimized, then we return the number as our answer.

The steps are as follows:

Call ‘solve’ function which is a recursive function with the parameters 0, 0, arr signifying the left, right pointer, and the given array, and we store the answer returned by it in k.
- If left is equal to ‘N’ then return 0;
- If right equals to ‘N’ or right less than left return 10^5;
- Initialize ‘ans’ with 10^5 to store the answer.
- If GCD of array[left] and array[right] is greater than 1 then store 1 + solve(right +1, right + 1, array) in ‘ans’.
- Store minimum of ‘ans’ and solve(right +1, left, array) in ‘ans’.
- Return the value of ‘ans’.
If k equals 10^5 or ‘k’ less than zero then return -1 else return ‘k’ as our final answer.

Solve now

02 Approach

We can place a start pointer at the beginning of the array and an end pointer at the end of the array. If Gcd(start, end) is greater than 1, then we return 1 as an answer else, we move the start pointer to the following index and check if it is possible to make such subarrays. The first and last elements of the original array will always be used. The first element will be used in the first split, and the last element will be used if there is a split at the end.

The steps are as follows:

Initialize ‘starting’ pointer to point to the first element of the array, ‘ending’ pointer to point to the end element of the array, and ‘numsubarrays’ to store the number of subarrays required.
Run a while loop as long as ‘ending’ is greater than equals zero:
- Run a for loop from starting = 0 to left <= ending:
  - If GCD of array[starting] and aray[ending] is greater than 1, then increase ‘numsubarrays’ by 1 and change ‘ending’ to ‘starting’ - 1 and break out of the loop.
- If ‘starting’ equals ‘ending’ and GCD of ‘starting’ and ‘ending’ equals 1, then return -1.
Return ‘numsubarrays‘ as the final answer.

Solve now