OPMIN - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Authors: shubham_grg
Testers: iceknight1093, tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have an array A of N integers between 1 and 100. Let M be its minimum.
In one move, you can change A_i to any integer you like between 1 and 100.
What’s the minimum number of moves needed to make M the maximum element?

EXPLANATION:

For M to be the maximum, the array can’t contain any elements larger than M.

So, every element larger than M requires at least one move, since it must be reduced to M (or something less than M).

Since M is the minimum element of the original array, the number of such elements is exactly N - x, where x is the number of times M appears in A.

So, use a loop to find x: the number of times M occurs in A.
Then, the answer is N - x.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(n - a.count(min(a)))
1 Like
2

We know the constraints for the range of Ai in the question, 1 ≤ Ai ≤ 100.

So can’t we just make all the occurrences of the minimum element equal to 100, then all the other will be either equal or less than 100, makin M the greatest element.

So if there are x occurrences of M, then we will have to change either x or n-x elements, whichever is minimum.

Can you tell me the problem with this approach?

3

I think you misunderstood the problem a bit.

Let’s say A = [1, 2, 2]. The minimum element is 1, so M = 1.

If you turn 1 into 100, the array is now [100, 2, 2]. Sure, 100 is the maximum, but M is still 1, and it isn’t the maximum!
Notice that the statement doesn’t change M: it’s the minimum value present in the array initially.

4

Okay, thanks for clearing that up.