Flip-Proof Numbers in a Range

Hard

Turn a sign with a number on it by 180° and the digits 0, 1 and 8 stay the same, 6 becomes 9 and 9 becomes 6. Every other digit stops being a digit at all. Call a number *flip-proof* if it reads exactly the same after that turn. For example, 69 and 818 are flip-proof, while 16 is not. You are given two strings lower and upper holding integers without leading zeros. Count the flip-proof numbers between lower and upper, both ends included.

Example 1

lower='10', upper='100' → 4

The range holds 11, 69, 88 and 96.

Example 2

lower='0', upper='9' → 3

Among single digits only 0, 1 and 8 are flip-proof: 6 turns into 9.

Example 3

lower='600', upper='700' → 3

These are 609, 619 and 689: the middle digit has to stay itself, while the outer 6 and 9 swap places in the turn.

Constraints

1 ≤ lower.length, upper.length ≤ 15
lower and upper consist of digits only and do not start with 0 unless the number is 0 itself
lower ≤ upper as numbers

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Array String

Similar problems

Numbers That Survive a Flip Medium Pattern With Dot and Star Hard Does the Text Fit the Pattern Hard Justify the Lines Hard Every Way to Space the Words Hard

Input

lower='10', upper='100'

Expected

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