Equal Elements

You are given an array A of size N.

In one operation, you can:

• Select indices i and j with i≠j

• Set Ai=Aj

You need to find the minimum number of operations required to make all elements of the array equal.

1. Problem Restatement

For each test case:

• You have an array A of size N.

• Operation: pick two positions i and j (i≠j) and assign Ai=Aj.

• After some operations, you want all elements of A to be the same.

Goal: Output the minimum number of operations needed.

Input Format:

• First line: integer T — number of test cases.

• For each test case:

• First line: integer N — array size.

• Second line: N space-separated integers — elements of array A.

Output Format:

• For each test case, print the minimum number of operations on a new line.

Constraints:

• 1 ≤ T ≤ 1000

• 1 ≤ N ≤ 2*105

• 1 ≤ Ai ≤ N

• Sum of all N over test cases ≤ 2*105

Sample:

Input:

3

3

1 2 3

4

2 2 3 1

4

3 1 2 4

Output:

2

2

3

Explanation (High Level):

• Test 1: [1, 2, 3]
  Make all equal to 2, for example: need to change 1 and 3 → 2 operations.

• Test 2: [2, 2, 3, 1]
  Best is to make all equal to 2 (since 2 appears twice). Need to change 3 and 1 → 2 operations.

• Test 3: [3, 1, 2, 4]
  All elements are distinct. No majority; any target value has frequency 1.
  We must change the other 3 elements → 3 operations.

2. Key Insight

In one operation, you can turn one element into the value of another element.

So if you decide that the final array value will be some number x, then:

• Every element that is already equal to x needs 0 operations.

• Every element that is not equal to x needs 1 operation (we copy from some index where the value is x).

Let:

• freq[v] = count of occurrences of value v in A.

• fmax = maximum frequency among all values.

If we choose the final array value as the one with frequency fmax (most frequent element), then:

• We already have fmax positions correct.

• We need to change the remaining N-fmax elements.

Therefore:

Minimum operations = N-fmax

because no other choice of target value can do better than picking the most frequent value.

3. Approach

Steps:

For each test case:

1. Read N.

2. Read array A of size N.

3. Count frequency of each value in A.

• Since 1 ≤ Ai ≤ N and N ≤ 2*105, we can use:

• A map/unordered_map, or

• A frequency array of size N+1.

4. Find fmax = maximum frequency.

5. Answer = N - fmax.

6. Print the answer.

Time & Space Complexity:

• Frequency counting per test: O(N)

• Finding maximum: O(N) or O(distinct values)

• Total across all tests: O(∑N) ≤ O(2*105)

Space: O(N) for frequencies in worst case, but fine under constraints.

This is optimal and easily fits within limits.

Pseudocode:

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code