Split array and GCD

Hard
0/120
3 upvotes
Asked in company
Directi

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
2 2 3 4 5 6 
3
1 2 3
Sample Output 1:
1 
-1
Explanation for Sample Output 1:
In the first test case, the subarray can be (2, 2, 3, 4, 5, 6) because GCD(2, 6) is 2 which is greater than 1. So we can create 1 subarray which is the minimum possible answer and we return it.

In the second test case, there is no possible subarray because the GCD of 1 and any element is always 1. So we cannot create any subarray. So we return -1 as our answer.
Sample Input 2:
2 
4
4 5 6 2  
2
3 2 3 4
3
Sample Output 2 :
1
2
Hint

Can you find all the possible subarrays?

Approaches (2)
Brute Force

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.
Time Complexity

O(2 ^ N), where N is the number of elements of the array.

 

As we are creating all possible partition so there are at most 2^N iterations. Hence, the overall complexity is O(2 ^ N).

Space Complexity

O(1)

 

No extra space required.

Code Solution
(100% EXP penalty)
Split array and GCD
Full screen
Console