Upside-Down Number Tiles

Medium

Door numbers are made of separate tiles, one per digit. A prankster turns every tile 180°, leaving each tile in its place. After the turn: - 0, 1 and 8 stay the same; - 2 and 5 turn into each other; - 6 and 9 turn into each other; - 3, 4 and 7 become unreadable. Every tile of a number is turned; none can be skipped. A number is *nicely spoiled* if afterwards it is still fully readable and has become a different number. How many numbers from 1 to n inclusive are nicely spoiled?

Example 1

n=7 → 3

2, 5 and 6 qualify. 1 turns into itself, and 3, 4 and 7 cannot be turned.

Example 2

n=12 → 5

On top of 2, 5, 6 and 9 comes 12, which turns into 15. 10 and 11 stay the same.

Example 3

n=1 → 0

1 turns into 1, so the number does not change.

Constraints

1 ≤ n ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming

Similar problems

Counting Grid Routes Medium Counting Search Tree Shapes Medium Every Bracketing Result Medium Numbers Made of Twos, Threes and Fives Medium Fewest Square Terms Medium

Input

n=7

Expected

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