Remove Adjacent solution codechef – You are given an arrayof length .
You can perform the following operation on the array, as long as it has more than one element:
- Choose any two adjacent elements, remove them from the array and insert their sum at that position.
- Formally, if the current length of the array is , you can choose an index , and transform the array into .
Note that after each operation, the length of array decreases by exactly.
Print the minimum number of operations to be applied on arraysuch that all the elements in the resulting array are equal. See sample explanation for more details.
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follows.
- Each test case consists of two lines of input.
- The first line contains an integer .
- The second line contains space-separated integers, the elements of array .
For each test case, output on a new line the minimum number of operations required to make all the elements equal.
- Sum of over all test cases does not exceed
Subtask #1 (100 points): Original constraints
Sample Input 1
4 3 5 2 3 2 6 9 5 3 6 5 4 9 3 3 3 3
Sample Output 1
1 1 2 0
Test case: It is optimal to remove and in the first operation, after which the array becomes — all of whose elements are equal.
Test case: Remove and after which the array becomes , which contains equal elements because it is of length .
Test case: First remove and after which the updated array becomes . Now remove and after which the array becomes .
Test case: The array elements are already equal.