# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}function solution(A) {2  const N = A.length3  const isPeak = (a, b, c) => a < b && b > c4  const checkFlagsValid = (flags, peaks) => {5    const N = peaks.length6    let flagsLeft = flags7    let i = 18    while (i < N - 1 && flagsLeft) {9      if (peaks[i]) {10        flagsLeft -= 111        i += flags12      } else {13        i += 114      }15    }16    return flagsLeft === 017  }18
19  const peaks = Array(N).fill(false)20  let peaksCount = 021  for (let i = 1; i < N - 1; i++) {22    if (isPeak(A[i - 1], A[i], A[i + 1])) {23      peaksCount++24      peaks[i] = true25    }26  }27
28  let maxFlags = Math.min(Math.ceil(Math.sqrt(N)), peaksCount)29  while (maxFlags) {30    if (checkFlagsValid(maxFlags, peaks)) {31      break32    }33    maxFlags--34  }35  return maxFlags36}```

## References

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

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

Search Posts