Editor

Make the Sum Divisible

#168 · Lists · Advanced · 165 XP · about 30 min

Write shortest_cut(nums, p) that finds the shortest subarray (a stretch of neighbouring items, possibly empty) you can remove from nums so that the sum of the remaining items is divisible by p, and returns its length.

You may not remove the whole list. Return -1 if it cannot be done.

Examples

shortest_cut([3, 1, 4, 2], 6)  # returns 1
shortest_cut([6, 3, 5, 2], 9)  # returns 2
shortest_cut([1, 2, 3], 3)     # returns 0
shortest_cut([1, 2, 3], 7)     # returns -1

In the first example the total is 10, and removing the 4 leaves 6. In the last example the only way to reach a multiple of 7 is to remove everything, which is not allowed.

Constraints

  • 1 <= len(nums) <= 100,000
  • 1 <= nums[i] <= 10**9
  • 1 <= p <= 10**9

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.