Codility MinAvgTwoSlice Solution in C++

Short Premise

Find the minimal average of any slice containing at least two elements.

Long Premise

Slice Definition

A non-empty array $A$ consisting of $N$ integers is given. A pair of integers $(P, Q)$, such that $ 0 \leq 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 let $A = (4,2,2,5)$

It contains the following slices:

  • slice $(0,1)$, whose average is $ (4 + 2)/2 = 3 $
  • slice $(1,2)$, whose average is $ (2 + 2)/2 = 2 $
  • slice $(2,3)$, whose average is $ (2 + 5)/2 = 7 / 2 $
  • slice $(0,2)$, whose average is $ (4 + 2 + 2)/3 = 8 / 3 $
  • slice $(1,3)$, whose average is $ (2 + 2 + 5)/3 = 3 $
  • slice $(0,4)$, whose average is $ (4 + 2 + 2 + 5)/4 = 13 / 4 $

The goal is to find the starting point of the minimal average slice.

Approach

Imagine a number $n$ in naturals. Let $m$ be the length of a vector $v$. This vector is in $\mathbb{R}^m$. Let $v_n$ be an element from this vector $v$.

The average of the elements of a contiguous vector from $v$ $ \text{dim}(v) \leq m$ is $\text{avg}_k(n) = [ v_n + v_{n+1} + \ldots + v_{n+k-1} ] / k$

We have to note that if

  • $k = 2$; $\text{avg}_2(n) = [ v_n+v_{n+1} ]/2$
  • $k = 3$; $\text{avg}_3(n) = [ v_n+v_{n+1}+v_{n+2} ]/3$
  • $k = 4$; $\text{avg}_4(n) = [ 2\text{avg}_2(n)+2\text{avg}_2(n+2) ]/4$
  • $k = 5$; $\text{avg}_5(n) = [ 2\text{avg}_2(n)+3\text{avg}_3(n+2) ]/5$

If $\text{avg}_k(n)$, k>3 is the minimum between all possible $\text{avg}_k(n)$ where $k>3$, this slice is decomposable into $\text{avg}_2(n)$ or $\text{avg}_3(n)$ parts and one of them should be the minimum average.

This is what a lot of fast algorithms take advantage. You have to figure out if some computing is being repeated. If this is happening you should use some strategy to avoid doing the same computation more than once, that is: storing in some data structure or taking strong conclusions from fewer passes as possible over the data set.

Code

// https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/
// Task Score: 100%
// Correctness: 100%
// Performance: 100%
// Detected time complexity: O(N)

#include <vector>
#include <limits>

int solution(std::vector<int> &A)
{

	double minimum = std::numeric_limits<double>::max();
	int minimum_idx = 0;

	auto avg_filter = [](std::vector<int>::iterator begin, std::vector<int>::iterator end) -> double {
		double avg = 0;
		double size = end - begin;

		for (auto it = begin; it < end; it++)
			avg += (double)*it;

		avg = avg / size;

		return avg;
	};

	auto minimum_update = [&](double value, int idx) -> void { if (value < minimum) { minimum = value; minimum_idx = idx; } };

	for (unsigned idx = 0; idx < A.size(); idx++)
	{

		double avg2, avg3;

		if ((idx + 1) < A.size())
		{
			avg2 = avg_filter(A.begin() + idx, A.begin() + idx + 2);
			minimum_update(avg2, (int)idx);
		}

		if ((idx + 2) < A.size())
		{
			avg3 = avg_filter(A.begin() + idx, A.begin() + idx + 3);
			minimum_update(avg3, (int)idx);
		}
	}

	return minimum_idx;
}
comments powered by Disqus