MinAvgTwoSlice
Task
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.
Solution
Firstly, note that if you have a slice that can be split into smaller slices, then the average of the slice cannot be less than the average of both of the sub-slices. So we only have to look at slices that cannot be split. This means slices of size 2 or 3.
In order to calculate the averages, I used the PrefixSums hack (though this doesn’t save much in this case)
#include <vector>
#include <cassert>
#include <climits>
#include <cfloat>
#include <algorithm>
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
size_t siz = A.size();
// contains partial sum of all elements up to NOT including
vector<int> sums(siz+1);
int sum =0;
sums[0]=0;
for (size_t i = 0; i < siz; i++) {
sum += A[i];
sums[i+1] = sum;
}
float mini = FLT_MAX;
int res = siz;
for (size_t i = 0; i < siz; i++) {
int maxLen = min(3,static_cast<int>(siz-i));
for (size_t j = 2;j <= maxLen; j++) {
float ave = static_cast<float>((sums[i+j] – sums[i])) / j;
if (ave < mini) {
res = i;
mini = ave;
}
}// for j
}// for i
return res;
}This solution is O(N)
Test Function
This code tests the solution
int main()
{
vector<int> A{4,2,2,5,1,5,8};
assert(solution(A) == 1);
vector<int> A2{4};
assert(solution(A2) == 1);
vector<int> A3{4,2,2,5,1,5,8,1,2};
assert(solution(A3) == 7);
vector<int> A4{4,2,2,5,1,5,8,1,3};
assert(solution(A4) == 1);
vector<int> A5{4,2,2,5,1,5,8,1,6,-2,9,-5};
assert(solution(A5) == 9);
return 0;
}Results
| Correctness | 100% |
| Performance | 100% |