[Solution] Distinct Colors CodeChef Solution

Problem

There are $N$ different types of colours numbered from $1$ to $N$. Chef has $A_i$ balls having colour $i$, $(1\le i \le N)$.

Chef will arrange some boxes and put each ball in exactly one of those boxes.
Find the minimum number of boxes Chef needs so that no box contains two balls of same colour.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases. The description of the test cases follows.
• The first line of each test case contains a single integer $N$, denoting the number of colors.
• The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ — denoting the number of balls having colour $i$.

Output Format

For each test case, output the minimum number of boxes required so that no box contains two balls of same colour.

Explanation:

Test case $1$: Chef needs at least $8$ boxes such that no box has two balls of same colour. A possible configuration of the $8$ boxes would be $\{[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1], [1], [1]\}$ where the $i^{th}$ element of this set denotes the colour of balls in the $i^{th}$ box.

Test case $2$: Chef needs at least $15$ boxes such that no box has two balls of same colour.

Test case $3$: Chef needs at least $4$ boxes such that no box has two balls of same colour. A possible configuration of the $4$ boxes would be $\{[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]\}$ where the $i^{th}$ element of this set denotes the colour of balls in the $i^{th}$ box.