A music box plays a sequence of note pitches, each represented as a positive integer pitch code, in a fixed order. A motif is any contiguous block of m consecutive pitch codes taken from the sequence. The music box is said to exhibit a recurring motif if there is some starting position in the sequence where a motif of length m repeats immediately after itself, without gaps or overlaps, for k or more repetitions in a row (so the repeated block together spans exactly m*k consecutive pitch codes).
Given the pitch sequence and the values m and k, determine whether the sequence exhibits such a recurring motif anywhere within it.
Line 1 contains three integers n, m, and k: the length of the pitch sequence, the motif length, and the required number of repetitions.
Line 2 contains n integers: the pitch codes, in playback order.
Print true if the sequence contains a length-m motif repeated k or more times consecutively somewhere within it, and false otherwise.
Example 1
Input
6 1 3 1 2 4 4 4 4
Expected
true
Explanation
With motif length 1, the pitch 4 appears three times in a row at the end of the sequence (positions 3, 4, 5), which is exactly the required 3 repetitions of a length-1 motif, so the answer is true.
Example 2
Input
6 2 3 1 2 1 2 1 3
Expected
false
Explanation
The length-2 motif [1, 2] repeats starting at position 0 and again at position 2, giving two full repetitions, but the block starting at position 4 is [1, 3], which breaks the pattern before a third repetition of [1, 2] is completed. No length-2 motif repeats 3 or more times consecutively, so the answer is false.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →