Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar
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.
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
O(N) per test case.