ADDPOS - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A of length N.
Find the minimum non-negative integer X such that adding X to every element of A results in A having non-negative sum.

EXPLANATION:

Let S = A_1 + A_2 + \ldots + A_N denote the initial sum of A.

Suppose we add X to every element of the array.
The sum of the elements now becomes:

(A_1 + X) + \ldots + (A_N + X) = (A_1 + \ldots + A_N) + N\cdot X = S + N\cdot X

So, we’re just looking for the smallest non-negative integer X such that S + N\cdot X \ge 0.

Note that the above inequality rearranges to \displaystyle X \ge \frac{-S}{N}.

So,

  • If S \ge 0, the answer is 0 since X = 0 works.
  • Otherwise, S \lt 0 and the answer is the smallest integer that’s \ge \frac{-S}{N}.
    This is, by definition, \text{ceil}\left(\frac{-S}{N}\right), i.e. the value \frac{-S}{N} rounded up.

Alternately, since the array elements are small, you can just iterate over X starting from 0 upwards, and check if S + N\cdot X \ge 0 is true.
Since -100 \le A_i, the answer is no more than 100 so this will terminate quickly.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    s = sum(a)
    for x in range(101):
        if s + n*x >= 0:
            print(x)
            break
1 Like