Show problems as
Classic problem #967MediumBacktrackingBreadth-First Search

Numbers With Same Consecutive Differences

Real-world version: Badge Codes With A Fixed Digit Step
Tracked in this browser only
Read Numbers With Same Consecutive Differences on LeetCode(opens in a new tab)

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

A site office issues badge codes. A code is a whole number written with exactly size digits, and the badge printer refuses a code whose first digit is 0, so no code may carry a leading zero.

The office also insists that neighbouring digits step by a fixed amount: for every pair of digits standing next to each other in the code, the absolute difference between them must equal gap exactly. A difference smaller or larger than gap is rejected, and the step may go up or down at each position.

Return every badge code the office would accept, as integers, in any order. When gap is 0 each digit has to match the one before it, so exactly one code exists per leading digit.

Examples

Example 1

Input
size = 2, gap = 7
Output
[18, 29, 70, 81, 92]

Every listed code has two digits whose absolute difference is 7: 1 and 8, 2 and 9, 7 and 0, 8 and 1, 9 and 2. The pair 0 and 7 also differs by 7 but `07` would start with a zero, so it is not a code.

Example 2

Input
size = 4, gap = 0
Output
[1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999]

A gap of 0 forces every digit to equal the digit before it, so each code is one digit written four times. `0000` is left out because a code may not begin with 0.

Example 3

Input
size = 3, gap = 9
Output
[909]

The only two digits nine apart are 0 and 9, so the digits have to alternate between them, and the code cannot begin with 0.

Constraints

  • 2 <= size <= 9
  • 0 <= gap <= 9

The values you return may be in any order.

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 badge_codes(size: int, gap: int) -> list[int]:
Java
public int[] badgeCodes(int size, int gap)

More on the same topics