93. Multiple of K Stretch
A fitness band records the change in step count for every minute of a workout in the array nums (values can be negative when the wearer walks backwards). A coach is looking for a tidy stretch: a contiguous run of at least two minutes whose recorded changes add up to a multiple of the integer k. Zero counts as a multiple of every k.
Return true if the workout contains at least one tidy stretch, otherwise return false. Note that the sum of a long stretch can exceed the 32-bit range, so keep your arithmetic safe.
Example 1
- Input:
- nums = [6,1,5,9], k = 6
- Output:
- true
- Explanation:
The stretch [1, 5] has a sum of 6, a multiple of 6, so the answer is true.
Example 2
- Input:
- nums = [3,5,8], k = 9
- Output:
- false
- Explanation:
The stretch sums are 8, 13 and 16, and none is divisible by 9, so the answer is false.
Constraints
1 ≤ nums.length ≤ 5 * 105
-109 ≤ nums[i] ≤ 109
1 ≤ k ≤ 2 * 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,800 msC++ 700 msJava 1,400 msJavaScript 1,400 msTypeScript 1,400 ms
Expected complexity
- Time
- O(n)
- Space
- O(min(n, k))