REMOVECARDS - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1039

PREREQUISITES:

None

PROBLEM:

There are N cards on a table, each with an integer from 1 to 10 written on them. What’s the least number of cards that you need to remove so that every remaining card has the same number on it?

EXPLANATION:

Since each card has a value between 1 and 10, the remaining cards can only have values in this range too.

Suppose we fix x, the value of the remaining cards. Then, it is optimal to remove all cards except those that have x written on them. The number of such cards can be found with a simple loop, going through each element of the array and checking whether it equals x or not.

Find this value for each x from 1 to 10. The final answer is the minimum of all these computed values.

Faster solutions exist, but are not needed to get AC on this problem.

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()))
    freq = [0] * 11
    for x in a:
        freq[x] += 1
    print(n - max(freq))
1 Like