Equal Operation
Problem
You are given an array \(A\) containing \(N\) integers. You can apply the following operation on the array:
- Choose an index \(i \;(1 \le i \le \mid A\mid)\), split \(A_i\) into two positive integers \(X, Y\) such that \(A_i = X+Y\), remove the \(i^{th}\) element from the array and append the elements \(X, Y\) to the array.
Find the minimum number of operations required to make all integers of the array equal.
Input format
- The first line contains \(T\) denoting the number of test cases. The description of \(T\) test cases is as follows:
- For each test case:
- The first line contains a single integer \(N\) denoting the size of array \(A\).
- The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) - denoting the elements of \(A\).
Output format
For each test case, print the minimum number of operations required to make all integers of the array equal.
Constraints
\(1 \leq T \leq 10^4 \\ 1 \leq N \leq 10^5\\ \\1\leq A_i \le 10^9 \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;2\cdot 10^5. \)
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
Test case 1: Choose i = 2 and split A[2] = 4 into X = 2, Y = 2 making A = [2, ,2, 2]. Now all elements of the array are equal.
Test case 2:
- Choose i = 2 and split A[2] = 2 into X = 1, Y = 1 making A = [1, 3, 1, 1].
- Choose i = 2 and split A[2] = 3 into X = 2, Y = 1 making A = [1, 1, 1, 2, 1].
- Choose i = 4 and split A[4] = 2 into X = 1, Y = 1 making A = [1, 1, 1, 1, 1, 1]. Now all elements of the array are equal.
