## 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.