Codility 'MinAvgTwoSlice' Solution | MartinKysel.com
Find the minimal average of any slice containing at least two elements.
MinAvgTwoSlice
Every slice must be of size two or three. Slices of bigger sizes are created from such smaller slices. Therefore should any bigger slice have an optimal value, all sub-slices must be the same, for this case to hold true. Should this not be true, one of the sub-slices must be the optimal slice. The others being bigger. Therefore we check all possible slices of size 2/3 and return the smallest one. The first such slice is the correct one, do not use <=!
why 3 elements?
Find the minimal average of any slice containing at least two elements.
MinAvgTwoSlice
A non-empty zero-indexed 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.
why 3 elements?
To check the number of the slots that produce the minimum average, we only have to check the sum of the consecutive two or three slots.
Think of the case in which there are the slice made of four slots. Let's assume these four slots can produce the minimum average.
The slice can be decomposed into two pairs, each of which consists two slots. If any of these pairs can produce a smaller average than the original four slots, then it contradicts the first assumption. If they produce a bigger average, then the other pair must be smaller than the average of the original four slots. So will be the same value. The same can be said to 5 slots (2+3), etc.
This can be said to any slice of an arbitrary size. If any sub-slice of a certain slice can produce a smaller average, then the original slice is not the slice that can produce a smaller portion. It the average values of the original slice and sub-slice are the same, we can simply take the index where the original slice starts, since what we need to return is the smallest index.
int solution(int A[], int N)
{
int i = 0;
if (N == 2){
return 0;
}
//initialize the current minimum average of the first two slots.
double minavg = (A[0] + A[1]) / 2.0;///
int idx = 0;
for (i = 2; i < N; i++){
double tmp1 = (A[i - 1] + A[i]) / 2.0;
double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
if (tmp1 < minavg){
idx = i - 1;
minavg = tmp1;
}
if (tmp2 < minavg){
idx = i - 2;
minavg = tmp2;
}
}
return idx;
}
def solution(A):
min_avg_value = (A[0] + A[1])/2.0 # The mininal average
min_avg_pos = 0 # The begin position of the first
# slice with mininal average
https://github.com/bluemihai/my-codility-solutions/blob/master/MinAvgTwoSlice.py
for index in xrange(0, len(A)-2):
# Try the next 2-element slice
if (A[index] + A[index+1]) / 2.0 < min_avg_value:
min_avg_value = (A[index] + A[index+1]) / 2.0
min_avg_pos = index
# Try the next 3-element slice
if (A[index] + A[index+1] + A[index+2]) / 3.0 < min_avg_value:
min_avg_value = (A[index] + A[index+1] + A[index+2]) / 3.0
min_avg_pos = index
# Try the last 2-element slice
if (A[-1]+A[-2])/2.0 < min_avg_value:
min_avg_value = (A[-1]+A[-2])/2.0
min_avg_pos = len(A)-2
return min_avg_pos
Read full article from Codility 'MinAvgTwoSlice' Solution | MartinKysel.com
Think of the case in which there are the slice made of four slots. Let's assume these four slots can produce the minimum average.
The slice can be decomposed into two pairs, each of which consists two slots. If any of these pairs can produce a smaller average than the original four slots, then it contradicts the first assumption. If they produce a bigger average, then the other pair must be smaller than the average of the original four slots. So will be the same value. The same can be said to 5 slots (2+3), etc.
This can be said to any slice of an arbitrary size. If any sub-slice of a certain slice can produce a smaller average, then the original slice is not the slice that can produce a smaller portion. It the average values of the original slice and sub-slice are the same, we can simply take the index where the original slice starts, since what we need to return is the smallest index.
def solution(A): min_idx = 0 min_value = 10001 for idx in xrange(0, len(A)-1): if (A[idx] + A[idx+1])/2.0 < min_value: min_idx = idx min_value = (A[idx] + A[idx+1])/2.0 if idx < len(A)-2 and (A[idx] + A[idx+1] + A[idx+2])/3.0 < min_value: min_idx = idx min_value = (A[idx] + A[idx+1] + A[idx+2])/3.0 return min_idxint solution(int A[], int N)
{
int i = 0;
if (N == 2){
return 0;
}
//initialize the current minimum average of the first two slots.
double minavg = (A[0] + A[1]) / 2.0;///
int idx = 0;
for (i = 2; i < N; i++){
double tmp1 = (A[i - 1] + A[i]) / 2.0;
double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
if (tmp1 < minavg){
idx = i - 1;
minavg = tmp1;
}
if (tmp2 < minavg){
idx = i - 2;
minavg = tmp2;
}
}
return idx;
}
def solution(A):
min_avg_value = (A[0] + A[1])/2.0 # The mininal average
min_avg_pos = 0 # The begin position of the first
# slice with mininal average
https://github.com/bluemihai/my-codility-solutions/blob/master/MinAvgTwoSlice.py
for index in xrange(0, len(A)-2):
# Try the next 2-element slice
if (A[index] + A[index+1]) / 2.0 < min_avg_value:
min_avg_value = (A[index] + A[index+1]) / 2.0
min_avg_pos = index
# Try the next 3-element slice
if (A[index] + A[index+1] + A[index+2]) / 3.0 < min_avg_value:
min_avg_value = (A[index] + A[index+1] + A[index+2]) / 3.0
min_avg_pos = index
# Try the last 2-element slice
if (A[-1]+A[-2])/2.0 < min_avg_value:
min_avg_value = (A[-1]+A[-2])/2.0
min_avg_pos = len(A)-2
return min_avg_pos
Read full article from Codility 'MinAvgTwoSlice' Solution | MartinKysel.com
