[Solution] Remove Adjacent solution codechef

Remove Adjacent solution codechef – You are given an array AA of length NN.

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 |A||A|, you can choose an index 1i<|A|1≤i<|A|, and transform the array into [A1,A2,,Ai1,Ai+Ai+1,Ai+2,,AN][A1,A2,…,Ai−1,Ai+Ai+1,Ai+2,…,AN].

Note that after each operation, the length of array decreases by exactly 11.

Print the minimum number of operations to be applied on array AA such that all the elements in the resulting array are equal. See sample explanation for more details.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines of input.
    • The first line contains an integer NN.
    • The second line contains NN space-separated integers, the elements of array AA.

Output Format

For each test case, output on a new line the minimum number of operations required to make all the elements equal.


  • 1T1041≤T≤104
  • 2N31042≤N≤3⋅104
  • 3104Ai3104−3⋅104≤Ai≤3⋅104
  • Sum of NN over all test cases does not exceed 31043⋅104


Subtask #1 (100 points): Original constraints

Sample Input 1 

5 2 3
6 9
3 6 5 4 9
3 3 3

Sample Output 1 



Test case 11: It is optimal to remove A2A2 and A3A3 in the first operation, after which the array becomes [5,5][5,5] — all of whose elements are equal.

Test case 22: Remove A1A1 and A2A2 after which the array becomes [15][15], which contains equal elements because it is of length 11.

Test case 33: First remove A3A3 and A4A4 after which the updated array AA becomes [3,6,9,9][3,6,9,9]. Now remove A1A1 and A2A2 after which the array becomes [9,9,9][9,9,9].

Test case 44: The array elements are already equal.

Leave a Comment