MINBOTTLES - Editorial

PROBLEM LINK:

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

Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N bottles, each with a capacity of X liters. The i-th bottle has A_i liters of water initially.
You can transfer water between bottles. What’s the minimum number of bottles needed to store all the water?

EXPLANATION:

Let \text{total} denote the total amount of water with us.
This can be computed as \text{total} = A_1 + A_2 + \cdots + A_N.

Each bottle can carry X liters of this water, so we need \frac{\text{total}}{X} bottles to carry all the water; plus maybe one extra if \text{total} is not a multiple of X since there will be a little bit leftover.

This can be represented by the ceiling function: the answer is

\left\lceil \frac{\text{total}}{X} \right\rceil

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    
    total = sum(a)
    reqd = (total + x - 1) // x
    print(reqd)