Strobogrammatic Number III

HardMathbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A **strobogrammatic** number reads the same after being rotated 180 degrees. Only the digits 0, 1, 6, 8, 9 survive rotation: 0, 1 and 8 map to themselves, while 6 and 9 map to each other. For example 69, 88 and 818 are strobogrammatic, but 66 and 12 are not. You are given two decimal strings low and high with low <= high numerically. Return how many strobogrammatic numbers x satisfy low <= x <= high. Numbers are written without leading zeros, so 0 itself counts but 080 is not a number. The bounds can have up to 15 digits, so iterating over the range is far too slow; build the candidates directly instead.

Examples

Input: low = "50", high = "100"
Output: 3
The strobogrammatic numbers in range are 69, 88 and 96.
Input: low = "0", high = "0"
Output: 1
0 rotates to itself.

Constraints

  • 1 <= low.length, high.length <= 15
  • `low` and `high` contain only digits
  • Neither has leading zeros unless it is exactly "0"
  • low <= high numerically

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems