MARBCOLL - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

Frequency arrays

PROBLEM:

There are M marble types, numbered 1 through M.
You have N marbles with you, of types A_1, \ldots, A_N.
How many marble types are you missing?

EXPLANATION:

Let \text{freq} be an array of length M, where \text{freq}[x] denotes the number of marbles of type x we have.

To construct this array:

  • Initialize the array \text{freq} to be of length M, filled with zeros.
  • Then, for each i from 1 to N, add 1 to \text{freq}[A_i].

At the end of this process, if \text{freq}[x] = 0 for any x, we don’t have any marbles of type x.
So, the answer is the number of x such that \text{freq}[x] = 0, which can be computed by iterating through the \text{freq} array.

TIME COMPLEXITY:

\mathcal{O}(N + M) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    freq = [0]*(m+1)
    for x in a:
        freq[x] += 1
    
    ans = 0
    for i in range(1, m+1):
        if freq[i] == 0:
            ans += 1
    print(ans)