Overview

Given that \(N\) students each nominate exactly one person to give a present to, find the number of students who did not receive a present from anyone.

Analysis

Each student \(i\) has a designated recipient \(T_i\) for their present. The key insight here is that the students who received at least one present are exactly the student numbers that appear among \(T_1, T_2, \ldots, T_N\).

For example, consider the case where \(N = 4\) and \(T = [2, 3, 2, 1]\).

Student	Recipient
1	2
2	3
3	2
4	1

• Student 1: Receives from student 4 → Received ✅
• Student 2: Receives from students 1 and 3 → Received ✅
• Student 3: Receives from student 2 → Received ✅
• Student 4: Receives from nobody → Did not receive ❌

The set of student numbers appearing in \(T\) is \(\{1, 2, 3\}\), which has \(3\) elements. Subtracting this from the total of \(4\) students, the answer is \(4 - 3 = 1\) student.

In other words, by counting the number of distinct values (values after removing duplicates) that appear in \(T\), we can determine the number of students who received a present. Subtracting that count from \(N\) gives the number of students who did not receive a present.

A naive approach of “for each student \(j\), linearly searching whether \(j\) exists in \(T\)” would be \(O(N^2)\), which could result in TLE when \(N\) is up to \(2 \times 10^5\).

Algorithm

1. Read \(T_1, T_2, \ldots, T_N\).
2. Convert the elements of \(T\) into a set. Since a set automatically removes duplicates, the number of elements in the set equals the number of students who received a present.
3. The answer is \(N\) minus the number of elements in the set.

\[\text{Answer} = N - |\{T_1, T_2, \ldots, T_N\}|\]

Complexity

• Time complexity: \(O(N)\) — Converting a list to a set takes an average of \(O(1)\) hash operations per element, resulting in \(O(N)\) overall.
• Space complexity: \(O(N)\) — Storing the set requires at most \(O(N)\) space.

Implementation Notes

• By using Python’s set, duplicate removal can be written concisely in a single line. Simply writing set(T) gives the set of distinct values contained in \(T\).

• There is no need to individually track “who each student received a present from”; it is sufficient to know just “the number of distinct student numbers designated as recipients.”

  Source Code

N = int(input())
T = list(map(int, input().split()))
received = set(T)
print(N - len(received))

---

This editorial was generated by claude4.6opus-thinking.