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] = 8contains 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:
function solution(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] = 8the 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].
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var min = 0;
var minIndex = 0;
for(var P = 0; P < A.length ; P++){
var sum = 0;;
var avg = 0;
for(var Q = P+1; Q < A.length; Q++){
if(sum == 0){
sum += A[P];
}
sum += A[Q];
console.log("> sum : " + sum);
avg = sum / ((Q - P) + 1);
if(avg < min || min == 0){
minIndex = P;
min = avg;
}
}
}
return minIndex;
}> sum : 6 > sum : 8 > sum : 13 > sum : 14 > sum : 19 > sum : 27 > sum : 4 > sum : 9 > sum : 10 > sum : 15 > sum : 23 > sum : 7 > sum : 8 > sum : 13 > sum : 21 > sum : 6 > sum : 11 > sum : 19 > sum : 6 > sum : 14 > sum : 13
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var min = 0;
var minIndex = 0;
for(var P = 0; P < A.length ; P++){
var sum = 0;;
var avg = 0;
for(var Q = P+1; Q < A.length; Q++){
if(sum == 0){
sum += A[P];
}
sum += A[Q];
avg = sum / ((Q - P) + 1);
if(avg < min || min == 0){
minIndex = P;
min = avg;
}
}
}
return minIndex;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var min = 0;
var minIndex = 0;
for(var P = 0; P < A.length ; P++){
var sum = 0;;
var avg = 0;
for(var Q = P+1; Q < A.length; Q++){
if(sum == 0){
sum += A[P];
}
sum += A[Q];
avg = sum / ((Q - P) + 1);
if(avg < min || min == 0){
minIndex = P;
min = avg;
}
}
}
return minIndex;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var min = 0;
var minIndex = 0;
for(var P = 0; P < A.length ; P++){
var sum = 0;;
var avg = 0;
for(var Q = P+1; Q < A.length; Q++){
if(sum == 0){
sum += A[P];
}
sum += A[Q];
avg = sum / ((Q - P) + 1);
if(avg < min || min == 0){
minIndex = P;
min = avg;
}
}
}
return minIndex;
}The following issues have been detected: wrong answers, timeout errors.
For example, for the input [10, 10, -1, 2, 4, -1, 2, -1] the solution returned a wrong answer (got 6 expected 5).
numbers from -1 to 1, N = ~100,000
running time: >6.00 sec., time limit: 0.59 sec.
all maximal values, N = ~100,000
running time: >6.00 sec., time limit: 0.62 sec.
many seqeneces, N = ~100,000
running time: >6.00 sec., time limit: 0.58 sec.