MinAvgTwoSlice

Find the minimal average of any slice containing at least two elements
ℹ️ © Codility, 2009-2018

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 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.

Assume that:
• 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].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solution

C#

class Solution {
  public int solution(int[] A) {
    int n = A.Length;
    if (n < 3) {
      return 0;
    }
    int r = 0;
    double m = 100000;
    for (int i = 0; i < n - 1; i++) {
      double t = (A[i] + A[i + 1]) / 2.0;
      if (t < m) {
        m = t;
        r = i;
      }
    }
    for (int i = 0; i < n - 2; i++) {
      double t = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
      if (t < m) {
        m = t;
        r = i;
      }
    }
    return r;
  }
}

Java

class Solution {
  public int solution(int[] A) {
    int n = A.length;
    if (n < 3) {
      return 0;
    }
    int r = 0;
    double m = 100000;
    for (int i = 0; i < n - 1; i++) {
      double t = (A[i] + A[i + 1]) / 2.0;
      if (t < m) {
        m = t;
        r = i;
      }
    }
    for (int i = 0; i < n - 2; i++) {
      double t = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
      if (t < m) {
        m = t;
        r = i;
      }
    }
    return r;
  }
}

JavaScript

function solution(A) {
  let n = A.length;
  if (n < 3) {
    return 0;
  }
  let r = 0;
  let m = 100000;
  for (let i = 0; i < n - 1; i++) {
    let t = (A[i] + A[i + 1]) / 2;
    if (t < m) {
      m = t;
      r = i;
    }
  }
  for (let i = 0; i < n - 2; i++) {
    let t = (A[i] + A[i + 1] + A[i + 2]) / 3;
    if (t < m) {
      m = t;
      r = i;
    }
  }
  return r;
}

PHP

function solution($A) {
  $n = count($A);
  if ($n < 3) {
    return 0;
  }
  $r = 0;
  $m = 100000;
  for ($i = 0; $i < $n - 1; $i++) {
    $t = ($A[$i] + $A[$i + 1]) / 2;
    if ($t < $m) {
      $m = $t;
      $r = $i;
    }
  }
  for ($i = 0; $i < $n - 2; $i++) {
    $t = ($A[$i] + $A[$i + 1] + $A[$i + 2]) / 3;
    if ($t < $m) {
      $m = $t;
      $r = $i;
    }
  }
  return $r;
}