Distinct Colors

You are given:

• N colors, numbered from 1 to N.

• For each color i, Chef has Ai balls of that color.

Chef will use some boxes.
Each ball must go into exactly one box.
Constraint: No box can contain two balls of the same color.

You must find the minimum number of boxes needed.

Problem Restatement

For each test case:

• You know how many balls of each color Chef has.

• You must place them into boxes such that:

• Each ball goes into exactly one box.

• A box can contain multiple balls, but all of different colors.

Goal: Minimize the number of boxes.

Input Format:

• First line: T — number of test cases.

• For each test case:

• First line: N — number of colors.

• Second line: N integers A1, A2, ...., An
  where Ai is the number of balls of color i.

Output Format:

• For each test case, print the minimum number of boxes required.

Constraints:

• 1 ≤ T ≤ 1000

• 2 ≤ N ≤ 100

• 1 ≤ Ai ≤ 105

Sample:

Input:

3

2

8 5

3

5 10 15

4

4 4 4 4

Output:

8

15

4

Explanation:

Test case 1

• Colors: 2

• Balls: color 1 → 8 balls, color 2 → 5 balls

• For color 1 (8 balls): a single box can only contain 1 ball of this color, so we need at least 8 boxes overall, no matter what.

• We can arrange as:

• 5 boxes with [1, 2]

• 3 boxes with [1]

• Total boxes = 8, which matches the maximum count among colors (max(A) = 8).

Test case 2

• Balls: [5, 10, 15]

• Color counts: 5, 10, 15 → the largest is 15.

• You need at least 15 boxes, because the color that appears 15 times must have its balls in 15 distinct boxes.

• It is always possible to place other colors into these boxes without violating the rule.

• Answer = 15.

Test case 3

• Balls: [4, 4, 4, 4]

• Each color has 4 balls, so max(A) = 4.

• We can use 4 boxes:

• Box 1: [1, 2, 3, 4]

• Box 2: [1, 2, 3, 4]

• Box 3: [1, 2, 3, 4]

• Box 4: [1, 2, 3, 4]

• No box has two balls of the same color.

• So the minimum number of boxes required is 4.

Intuition and Key Observation

In any single box:

• You can have at most 1 ball of each color.

Consider some color i with Ai balls:

• These Ai balls must be placed in different boxes (since no box can contain two balls of color i).

• Therefore, the number of boxes must be at least Ai for each color i.

So, over all colors:

• The number of boxes must be at least max(A1, A2, ...., An).

Now the crucial question:
Is it always possible to do it with exactly max(Ai) boxes?

Yes:

• Let M = max(Ai).

• We create M boxes.

• For each color i, place one ball of color i into a different box each time, spreading its Ai balls across at most M boxes.

• Since Ai ≤ M for every color, we will never need more than M boxes for any color.

• There is no upper limit on how many different colors can be in one box, so this packing is always possible.

Therefore:

Answer = max1 ≤ i ≤ NAi

Approach

Step-by-step:

For each test case:

1. Read integer N.

2. Read array A of length N.

3. Compute the maximum value in A, call it maxA.

4. Print maxA.

Time & Space Complexity:

• Per test case: O(N) to read and find maximum.

• Total over all test cases: O(∑N), which is easily within the limits.

• Space: O(1) extra (besides the input array).

Pseudocode:

Java code

C code

C++ code

Python code

JavaScript code