0674MediumMathDynamic Programming

Twin Ticket Numbers on a Flip Panel

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_twins(limit: int) -> int:

Java

public int countTwins(int limit)

The intended approach

Time O(limit): one table entry per number, each filled in constant time.Space O(limit) for the table of kinds.

Sort every number from `1` to `limit` into one of three kinds: it goes unreadable when flipped, it stays readable and reads the same, or it stays readable and reads differently. A number's kind follows from the kind of the number with its last digit chopped off, together with that last digit: the whole number is unreadable if either part is, and it reads differently if either the chopped-off part read differently or the last module is one of the four that swaps. Fill the kinds in increasing order, handling one-module numbers directly, and count the third kind.

Pythonentry point: count_twins

def count_twins(limit):
    # O(limit) table: 0 unreadable when flipped, 1 readable and unchanged, 2 readable and changed
    same = (0, 1, 8)
    swaps = (2, 5, 6, 9)
    kind = [0] * (limit + 1)
    twins = 0
    for x in range(1, limit + 1):
        if x < 10:
            if x in same:
                kind[x] = 1
            elif x in swaps:
                kind[x] = 2
            else:
                kind[x] = 0
        else:
            head = kind[x // 10]
            last = x % 10
            if head == 0 or (last not in same and last not in swaps):
                kind[x] = 0
            elif head == 2 or last in swaps:
                kind[x] = 2
            else:
                kind[x] = 1
        if kind[x] == 2:
            twins += 1
    return twins

The obvious version

Walk every number in the range, write it out digit by digit and look each digit up in a table of what the module shows when flipped. Skip the number if any digit has no entry, otherwise compare the flipped text with the original text and count it when they differ.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_twins(limit):
    face = {"0": "0", "1": "1", "8": "8", "2": "5", "5": "2", "6": "9", "9": "6"}
    total = 0
    for x in range(1, limit + 1):
        text = str(x)
        flipped = ""
        readable = True
        for ch in text:
            if ch not in face:
                readable = False
                break
            flipped += face[ch]
        if readable and flipped != text:
            total += 1
    return total

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in