FilesExpand file tree

master

/

Lesson_005_MinAvgTwoSlice.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

90 lines (63 loc) · 2.64 KB

master

/

Lesson_005_MinAvgTwoSlice.js

Copy path

Top

File metadata and controls

• Code
• Blame

90 lines (63 loc) · 2.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

const MinAvgTwoSlice = {

solution: function(A) {

let len = A.length;

let orig_len = len;

let res_p = 0;

let avg = (A[0] + A[1]) / 2.0; // starting minimum average

// turn array into prefix sums array, we can use this to speed up calculation of intervals

for (let i=1; i<len; i++) {

A[i] += A[i-1];

}

A.unshift(0); // add sum for prefix_0

// only need to return the starting index of the slice with the

// lowest average, so ignore slices larger than 3 - see https://github.com/daotranminh/playground/blob/master/src/codibility/MinAvgTwoSlice/proof.pdf

// however, this solution also works without the line below

len = 3.0;

while (len >= 2) {

let p = 0;

while (len+p <= orig_len) {

let q = p + len;

let sum = A[q] - A[p];

let new_avg = sum / len;

if ((new_avg < avg) || ((new_avg == avg) && (p < res_p))) {

avg = new_avg;

res_p = p;

}

p++;

}

len--;

}

return res_p;

}

}

result = MinAvgTwoSlice.solution([4, 7]);

console.log(`${result}, pass: ${result == 0}`);

result = MinAvgTwoSlice.solution([4, 2, 2, 5]);

console.log(`${result}, pass: ${result == 1}`);

result = MinAvgTwoSlice.solution([2, 2, 2, 5]);

console.log(`${result}, pass: ${result == 0}`);

result = MinAvgTwoSlice.solution([4, 2, 2, 2]);

console.log(`${result}, pass: ${result == 1}`);

result = MinAvgTwoSlice.solution([4, 3, 2, 2]);

console.log(`${result}, pass: ${result == 2}`);

result = MinAvgTwoSlice.solution([4, 3, 2, 2, 5]);

console.log(`${result}, pass: ${result == 2}`);

result = MinAvgTwoSlice.solution([4, 3, 2, 2, 1]);

console.log(`${result}, pass: ${result == 3}`);

result = MinAvgTwoSlice.solution([4, 3, 2, 2, 1, 9]);

console.log(`${result}, pass: ${result == 3}`);

result = MinAvgTwoSlice.solution([4, 2, 2, 5, 1, 5, 8]);

console.log(`${result}, pass: ${result == 1}`);

result = MinAvgTwoSlice.solution([1, 4, 2, 5, 3, 5, 1, 5, 8]);

console.log(`${result}, pass: ${result == 0}`);

result = MinAvgTwoSlice.solution([4, 2, 5, 3, 5, 1, 5, 8]);

console.log(`${result}, pass: ${result == 0}`);

result = MinAvgTwoSlice.solution([4, 2, 5, 2, 5, 1, 5, 1, 8]);

console.log(`${result}, pass: ${result == 5}`);

result = MinAvgTwoSlice.solution([8, 4, 2, 5, 3, 5, 1, 5]);

console.log(`${result}, pass: ${result == 1}`);

result = MinAvgTwoSlice.solution([5, 5, 5, 5, 5, 5, 5]);

console.log(`${result}, pass: ${result == 0}`);

result = MinAvgTwoSlice.solution([7, 6, 5, 4, 3, 2, 1]);

console.log(`${result}, pass: ${result == 5}`);

// TESTED AND PASSED ON Codility - 100% on everything but there are faster solutions without using the prefix sums method