Count Elements Greater Than Previous Average
Difficulty: Easy.
Given an array of positive integers, return the number of elements that are strictly greater than the average of all previous elements. Skip the first element.
Example
Input
responseTimes = [100, 200, 150,300]
Output
2
Explanation
- Day 0: 100 (no previous days, skip)
- Day 1: 200 > average(100) = 100 → count = 1
- Day 2: 150 vs average(100, 200) = 150 → not greater → count = 1
- Day 3: 300 > average(100, 200, 150) = 150 → count = 2 Return 2.
Input Format
- The first line contains an integer n (0 ≤ n ≤ 1000), the number of days.
- If n > 0, the next n lines contains an integer representing responseTimes[i].
- If n = 0, the second line is omitted or empty.
Example
4
100
200
150
300
here 4 is the length of array, followed by the elements of array on each line.
Constraints
- 0 <= responseTimes.length <= 1000
- 1 <= responseTimes[i] <= 10^9 for 0 <= i < responseTimes.length
Output Format
- A single integer depicting the count of days.
1. When length of vector is less than 2, the output is always 0.
2. 10^9 * 1000 > 2^32. So, a normal 32 bits integer couldn't represent big enough summation. Therefore, set "long sum;".
3. Can't use "responseTimes[i] * i" (Exceeds range of 2^32). Has to divide sum with i and compare with responseTimes[i].
Code:
/*
* Complete the 'countResponseTimeRegressions' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY responseTimes as parameter.
*/
int countResponseTimeRegressions(vector<int> responseTimes) {
int n = responseTimes.size();
//cout << "n = " << n << "\n";
long sum=0;
if (n==0) return 0;
if (n==1) return 0;
sum = (long) responseTimes[0];
int i, count=0;
for (i=1;i<n;i++) {
if (responseTimes[i]>sum/i) {
count++;
}
sum+=responseTimes[i];
}
return count;
}
