Show problems as
Classic problem #974MediumArrayHash TablePrefix Sum

Subarray Sums Divisible by K

Real-world version: Full Turn Command Blocks
Tracked in this browser only
Read Subarray Sums Divisible by K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstPrefix Sums · Dynamic Programming, animated step by step

A turntable is driven by a stepper motor that takes perTurn steps to bring the platter round once. You are given the queue of commands sent to the motor: steps[i] is a signed step count, positive to drive the platter forward and negative to drive it back.

A block is one or more commands that sit next to each other in the queue. A block is settling when running only that block leaves the platter pointing the way it pointed before the block began, which happens exactly when the step counts in the block add up to a multiple of perTurn. Negative multiples count, and so does a total of zero.

Return how many settling blocks the queue holds.

Examples

Example 1

Input
steps = [4, 5, 0, -2, -3, 1], perTurn = 5
Output
7

Seven blocks total a multiple of 5: the whole queue at 5, `[5]`, `[5, 0]`, `[5, 0, -2, -3]` at 0, `[0]`, `[0, -2, -3]` at -5 and `[-2, -3]` at -5.

Example 2

Input
steps = [-1, 4], perTurn = 4
Output
1

The block `[4]` totals 4, while `[-1]` totals -1 and `[-1, 4]` totals 3, neither of which is a multiple of 4.

Example 3

Input
steps = [2, -2, 2, -2], perTurn = 2
Output
10

Every command is already a multiple of 2, so each of the ten blocks totals a multiple of 2 as well.

Constraints

  • 1 <= steps.length <= 3 * 10^4
  • -10^4 <= steps[i] <= 10^4
  • 2 <= perTurn <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_settling_blocks(steps: list[int], perTurn: int) -> int:
Java
public int countSettlingBlocks(int[] steps, int perTurn)

More on the same topics