Show problems as
Classic problem #3129MediumDynamic ProgrammingPrefix Sum

Find All Possible Stable Binary Arrays I

Real-world version: Settled Control Tapes
Tracked in this browser only
Read Find All Possible Stable Binary Arrays I on LeetCode(opens in a new tab)

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

A punch machine writes a control tape one cell at a time. Each cell ends up holding either the value 0 or the value 1, and the finished tape must hold exactly zero cells of value 0 and exactly one cells of value 1, so its length is always zero + one.

The reader that consumes the tape loses synchronisation if it ever passes a long stretch of identical cells. A tape is therefore called settled when every maximal block of equal neighbouring cells holds at most limit cells; equivalently, nowhere on the tape do limit + 1 consecutive cells carry the same value.

Two tapes are different when they differ in at least one position. Count the settled tapes and report that count as a remainder after division by 1000000007.

Examples

Example 1

Input
zero = 2, one = 2, limit = 1
Output
2

Writing a tape as its run of cell values, the settled tapes are `0101` and `1010`. Every block in each one holds a single cell, which is within `limit = 1`.

Example 2

Input
zero = 2, one = 3, limit = 2
Output
7

The seven settled tapes are `01011`, `01101`, `10011`, `10101`, `10110`, `11001` and `11010`. Each holds two `0` cells and three `1` cells, and no block in any of them is longer than two.

Example 3

Input
zero = 4, one = 3, limit = 7
Output
35

`limit = 7` is at least the tape length, so no arrangement can violate the block rule and every ordering of four `0` cells and three `1` cells counts.

Constraints

  • 1 <= zero <= 200
  • 1 <= one <= 200
  • 1 <= limit <= 200

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 number_of_stable_arrays(zero: int, one: int, limit: int) -> int:
Java
public int numberOfStableArrays(int zero, int one, int limit)

More on the same topics