PROBLEM LINK:
Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar
DIFFICULTY:
Easy
PREREQUISITES:
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.