Codility: Flags Solution

Lesson 10 Prime and Composite Numbers

Approach

(Flag is on the peak only)

Maximum number of peaks is upper bound of

sqrt(N)
(
N
is the length of
A
)

Get an array of peaks to determine whether an index is peak

Decrease from max peaks, for each iteration, check if that the number of peak is valid

The number of peak is whether valid or not is based on the condition: distance between any 2 flag should be >= number of flags

Implementation

1function solution(A) {
2 const N = A.length
3 const isPeak = (a, b, c) => a < b && b > c
4 const checkFlagsValid = (flags, peaks) => {
5 const N = peaks.length
6 let flagsLeft = flags
7 let i = 1
8 while (i < N - 1 && flagsLeft) {
9 if (peaks[i]) {
10 flagsLeft -= 1
11 i += flags
12 } else {
13 i += 1
14 }
15 }
16 return flagsLeft === 0
17 }
18
19 const peaks = Array(N).fill(false)
20 let peaksCount = 0
21 for (let i = 1; i < N - 1; i++) {
22 if (isPeak(A[i - 1], A[i], A[i + 1])) {
23 peaksCount++
24 peaks[i] = true
25 }
26 }
27
28 let maxFlags = Math.min(Math.ceil(Math.sqrt(N)), peaksCount)
29 while (maxFlags) {
30 if (checkFlagsValid(maxFlags, peaks)) {
31 break
32 }
33 maxFlags--
34 }
35 return maxFlags
36}

References

https://codility.com/media/train/solution-flags.pdf

Comments

Loading comments...

Tags

codility

Next Post

Codility: CountFactors

Jan 26, 2021

Lesson 10 Prime and Composite Numbers

Previous Post

Codility: MinPerimeterRectangle

Jan 26, 2021

Lesson 10 Prime and Composite Numbers

HoningJS

Search Posts