0267MediumArrayHash TablePrefix Sum

Full Turn Command Blocks

Tracked in this browser only

Trains the technique from

LeetCode 974Subarray Sums Divisible by K

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_settling_blocks(steps: list[int], perTurn: int) -> int:

Java

public int countSettlingBlocks(int[] steps, int perTurn)

The intended approach

Time O(n)Space O(min(n, perTurn)) for the tally of remainders

Keep the running total of every command from the head of the queue. A block totals a multiple of `perTurn` exactly when the running totals just before it and at its end leave the same remainder, so a tally of how many prefix positions produced each remainder turns the count into a lookup: at each command, add the tally already held for the current remainder, then record the current remainder. The tally starts with one entry for remainder 0, which stands for the empty prefix and is what lets blocks beginning at the first command be counted. Python's remainder operator already lands in `0 .. perTurn - 1` for a positive divisor, so a negative running total needs no separate correction.

Pythonentry point: count_settling_blocks

def count_settling_blocks(steps, perTurn):
    seen = {0: 1}
    total = 0
    running = 0
    for step in steps:
        running += step
        rest = running % perTurn
        total += seen.get(rest, 0)
        seen[rest] = seen.get(rest, 0) + 1
    return total

The obvious version

Fix each starting command, extend the block one command at a time keeping its total, and count every total that is a multiple of `perTurn`. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_settling_blocks(steps, perTurn):
    n = len(steps)
    total = 0
    for i in range(n):
        block = 0
        for j in range(i, n):
            block += steps[j]
            if block % perTurn == 0:
                total += 1
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in