MinAvgTwoSlice at app.codility.com-programmers in C Plus Plus Explained - Find the minimal average of any slice containing at least two elements
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 29 Jan 2024
Task
Detected time complexity : O(N)
Lesson 5 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 <= P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q - P + 1).
For example, array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
contains the following example slices:
slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal.
Write a function:
int solution(vector<int> &A);
that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
For example, given array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [-10,000..10,000].
Note:
A slice is a sequence of elements that form a subset (subgroup) of the array. For this problem, note that a slice has a minimum length of 2.
Average value does not necessarily increase as the number of elements in the slice increases (even if all the elements are positive).
Brute Force Approach
The brute force method calculates the averages for all the possible slices, beginning from the slice at index 0. The program is:
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
double minAvg = 1000000000; //start with the highest possible number
int startingPos = 0;
for(int i=0; i < N-1; i++) {
double sum = A[i];
for (int j=i+1; j < N; j++) {
sum = sum + A[j];
double difference = j - i + 1;
double avg = sum/difference;
if (avg < minAvg) {
minAvg = avg;
startingPos = i;
}
}
}
return startingPos;
}
int main()
{
vector<int> P{4, 2, 2, 5, 1, 5, 8};
int ret = solution(P);
cout << ret <<'\n';
vector<int> P2{-3, -5, -8, -4, -10};
int ret2 = solution(P2);
cout << ret2 <<'\n';
return 0;
}
At app.codility.com/programmers the scoring and detected time complexity for this solution() function is:
Task score : 60% - Correctness : 100% ; Performance : 20%
Detected time complexity: O(N2)
Smart Approach
With that knowledge accepted, the solution() function can do the prefix sums for the whole array first. After that, re-scan the whole array again to obtain the minimum average for two or three consecutive elements. All that will take (N + N) operations. This is illustrated in the following table.
Recall: The normal way to obtain a slice sum is as follows: Subtract the prefix sum at the beginning of the slice, from the prefix sum just after the slice.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| A elems. | 4 | 2 | 2 | 5 | 1 | 5 | 8 | |
| P. sums | 0 | 4 | 6 | 8 | 13 | 14 | 19 | 27 |
| Aver. in 2's | (6-0)/2 = 3 | (8-4)/2 = 2 | (13-6)/2 = 3.5 | (14-8)/2 = 3 | (19-13)/2 = 3 | (27-14)/2 = 6.5 | ||
| Aver. in 3's | (8-0)/2 = 4 | (13-4)/2 = 4.5 | (14-6)/2 = 4 | (19-8)/2 = 5.5 | (27-13)/2 = 7 |
It is possible to do the prefix sums, as well as be checking for the average of two or three consecutive elements, in one scan, to obtain N major operations. The smart solution (program) code in O(N) time is (read the comments as well):
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
int P[N+1]; //prefix array with element for preceding zero
P[0] = 0;
P[1] = P[0] + A[0];
P[2] = P[1] + A[1];
double minAvg = (P[2] - P[0])/2.0; //first average for first two elements
int minIndex = 0;
for (int i=3; i<=N; i++) { // <=N because of N+1 for prefix sums, zero based indexing
P[i] = P[i-1] + A[i-1];
if ((P[i]-P[i-2])/2.0 < minAvg) { //slice average of two elements
minIndex = i-2;
minAvg = (P[i] - P[i-2])/2.0;
}
if ((P[i]-P[i-3])/3.0 < minAvg) { //slice average of three elements
minIndex = i-3;
minAvg = (P[i] - P[i-3])/3.0;
}
}
return minIndex;
}
int main()
{
vector<int> P{5, 2, 2, 5, 1, 5, 8};
int ret = solution(P);
cout << ret <<'\n';
vector<int> P2{-3, -5, -8, -4, -10};
int ret2 = solution(P2);
cout << ret2 <<'\n';
return 0;
}
The loop begins with i=3, because i=2 has already been taken into consideration with the statements:
P[2] = P[1] + A[1];
and
double minAvg = (P[2] - P[0])/2.0;
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
The first code segment in the solution() function is not included in the determination of the overall time complexity, by app.codility.com/programmers.
Note that the calculations have been done with the double number type, because, based on the assumptions given by the problem (task), the whole number parts and the fractional parts of numbers can be very large.
Conclusion
In order to solve similar problems, develop the prefix sums as the averages for two and three consecutive elements are calculated.
The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.