# ZOZ - Editorial

Practice

Author: Misha Chorniy

Tester: Lewin Gan

Easy

None

## PROBLEM:

You are given an array A with size N and a number K. You need to find number of valid positions in the array. A position i (1 \le i \le N) is valid if, after increasing A[i] by K, it would be greater than the sum of all other elements in the array A.

## EXPLANATION:

A position i (1 \le i \le N) is valid if, after increasing A[i] by K, it would be greater than the sum of all other elements in the array A. Hence, for position i to be valid, we can write A[i]+K>T-A[i], where T represents the sum of entire array. We will compute the value of T in one pass of the array. In next pass, we will check how many positions are valid using the above condition. A pseudo-code to illustrate this:

``````def solve(A,N,K):
T=0
for i = 1...N:
T+=A[i]
ANS=0
for i = 1...N:
if (A[i]+K)>(T-A[i]):
ANS+=1
return ANS
``````

## Time Complexity:

O(N) per test case.

## AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution