Numbers With Neighbouring Digits

Medium

Call a non-negative integer a **staircase number** if every two adjacent digits in it differ by exactly 1. For example, 1012 and 7 are staircase numbers, while 1013 is not. You are given low and high. Return all staircase numbers in the range [low, high] inclusive, in increasing order.

Example 1

low=30, high=80 → [32, 34, 43, 45, 54, 56, 65, 67, 76, 78]

In 32, 34, 43, 45, 54, 56, 65, 67, 76, 78 adjacent digits differ by 1. Numbers like 33 or 40 do not qualify.

Example 2

low=0, high=11 → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Every single-digit number qualifies since it has no adjacent digits. Among two-digit numbers up to 11 only 10 does.

Example 3

low=900, high=1000 → [987, 989]

Constraints

0 ≤ low ≤ high ≤ 2·10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Math Backtracking

Similar problems

Mirrored One-Bit Codes Medium Fewest Square Terms Medium Numbers Without Repeated Digits Medium Exact Volume With Two Buckets Medium A Four-Button Lamp Panel Medium

Input

low=30, high=80

Expected

[32, 34, 43, 45, 54, 56, 65, 67, 76, 78]

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.