PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Utkarsh Gupta
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh
DIFFICULTY:
760
PREREQUISITES:
Observation
PROBLEM:
You have A_i balls of color i. What’s the minimum number of boxes needed so that you can put the balls into boxes such that no box contains two or more balls of the same color?
EXPLANATION:
Suppose we had K boxes.
Then, if some A_i \gt K, we wouldn’t be able to put all A_i balls of this color into distinct boxes: at least one would remain.
This means we want K \geq A_i for every i.
So, the answer is simply \max(A_1, A_2, \ldots, A_N), which is the smallest integer satisfying this condition.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(max(map(int, input().split())))