Show problems as
Classic problem #788MediumMathDynamic Programming

Rotated Digits

Real-world version: Twin Ticket Numbers on a Flip Panel
Tracked in this browser only
Read Rotated Digits on LeetCode(opens in a new tab)

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

A cloakroom prints ticket numbers on a panel of flip modules, one module per digit and no extra zero in front. Turning the panel over changes what each module shows, and every module keeps its place in the number:

  • 0, 1 and 8 show the same digit as before,
  • 2 shows 5 and 5 shows 2,
  • 6 shows 9 and 9 shows 6,
  • 3, 4 and 7 show a shape that is not a digit.

A ticket number is a twin when, after the panel is turned over, every module still shows a digit and the number read off the panel is not the number that was printed.

Count the twins among the ticket numbers 1 through limit.

Examples

Example 1

Input
limit = 68
Output
28

The twins counted here include the one-module numbers 2, 5, 6 and 9, and two-module numbers such as 12, 15, 20, 25, 51, 62 and 68. For instance 68 flips to 98, which is readable and different, while 88 flips to itself and 63 leaves an unreadable module.

Example 2

Input
limit = 500
Output
130

Numbers such as 96 (which flips to 69) and 205 (which flips to 502) are twins, while 101 flips to 101 and 400 has an unreadable module.

Example 3

Input
limit = 9457
Output
2124

Among the four-module numbers, 8596 is a twin because it flips to 8269, but 1801 is not because it flips to itself.

Constraints

  • 1 <= limit <= 10^4

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 count_twins(limit: int) -> int:
Java
public int countTwins(int limit)

More on the same topics