Tree, digit and bitmaskhardCount the complement with a digit scan over a bound4 min · 237 of 290

Bays the reader flags

Count the parking bays whose number repeats a digit, by counting the bays that do not and walking the bound digit by digit.

A council numbers its kerbside bays 1, 2, 3 and upward. The plate reader misfiles any bay whose number uses the same digit twice, and the audit wants to know how many bays that is.

The problem

Bays carry the numbers 1 through highest, painted without leading zeros. A bay is flagged when some digit appears more than once in its number. Bay 121 is flagged, because the 1 appears twice. Bay 120 is not. Bay 100 is flagged, on the two zeros. Every one-digit bay is clean, since one digit cannot repeat.

Count the flagged bays among 1 through highest.

Input. highest — a positive integer, the number of the last bay.

Output. How many bays from 1 to highest repeat a digit.

Example.

highest = 250   ->  55

Below 100 only the nine doubles are flagged: 11, 22, and so on to 99. Between 100 and 250 another 46 are flagged — 100, 101, 110, 121, 200 and 233 among them — for 55 in all.

Example, a longer run:

highest = 4000   ->  1750

261 of the bays below 1000 are flagged, and 1489 of those from 1000 to 4000. Roughly half of the four-digit bays repeat a digit, which is what makes the direct count awkward and the complement easy.

Constraints.

  • 1 <= highest <= 10^9

Hints

Hint 1

"Some digit repeats" has no clean multiplication rule. Its opposite does: count the bays whose digits are all different, then subtract.

Hint 2

For a clean number with L digits, the first digit has 9 choices — no leading zero — and each later one has whatever is left of the ten digits.

Hint 3

For numbers with as many digits as highest, walk its digits from the left, holding the set the matched prefix has used. If highest repeats a digit itself, the walk cannot go past that point.

Approach

Brute force

Convert each of 1 through highest to a string and compare the length of its digit set with its length. At 10^9 bays that is a billion conversions, about 10^10 character operations.

The insight

Count the bays that are not flagged — the ones with all-different digits — and subtract from highest, because all-different is a falling factorial while "at least one repeat" is not.

Once a prefix is fixed and uses u distinct digits, each remaining position chooses from what is left: 10 - u, then 9 - u, and so on. That product is the whole count. The precondition is the same one every bound scan needs: a number below highest with the same digit count has a first position where it goes lower, and grouping by that position counts each number once.

Algorithm

  1. Take the digits of highest; call the count n.
  2. For each shorter length L, add 9 * 9 * 8 * ... with L factors to the clean total.
  3. Walk the digits from the left, holding used, the digits of the matched prefix.
  4. At position i, for each candidate below that digit that is not in used — and not 0 when i is 0 — multiply out the falling factorial over the remaining positions and add it.
  5. If the digit of highest is already in used, stop: no longer prefix can be clean.
  6. If the walk finishes, add 1 for highest itself, then return highest - clean.

Complexity

Time O(n^2 · 10) with n at most 10 digits — a few hundred steps regardless of how large highest is. Space O(1) beyond the digit set of the prefix.

Solution

Python 3 · standard library38 lines · 6 test cases, all passing
"""Bays the reader flags — count the all-distinct numbers and subtract."""


def all_distinct_upto(highest):
    """How many of 1..highest use no digit twice."""
    bound = [int(c) for c in str(highest)]
    n = len(bound)

    total = 0
    for length in range(1, n):
        count, pool = 9, 9                # 9 leading digits, then the shrinking pool
        for _ in range(length - 1):
            count *= pool
            pool -= 1
        total += count

    used = set()
    for i, digit in enumerate(bound):
        low = 1 if i == 0 else 0
        for candidate in range(low, digit):
            if candidate in used:
                continue
            # prefix now strictly below the bound, so the tail is a falling
            # factorial over the digits neither the prefix nor this one took
            tail, pool = 1, 9 - len(used)
            for _ in range(n - i - 1):
                tail *= pool
                pool -= 1
            total += tail
        if digit in used:
            return total                  # the bound repeats: no longer prefix survives
        used.add(digit)
    return total + 1                      # the bound itself has all-distinct digits


def solve(highest):
    """How many bay numbers in 1..highest repeat a digit."""
    return highest - all_distinct_upto(highest)
The cases that ran
TESTS = [
    ((250,), 55),
    ((4000,), 1750),
    ((4477,), 2003),                      # the bound repeats a digit itself
    ((9,), 0),
    ((100,), 10),
    ((1000000000,), 994388230),
]

Pitfalls

  • Allowing a leading zero in the shorter lengths. Using 10 * 9 * 8 instead of 9 * 9 * 8 counts numbers like 042, inflates the clean total and pushes the flagged answer too low.
  • Walking past a repeat inside highest. With highest = 4477 the prefix 44 is already dirty, so nothing longer can match it; continuing adds counts for prefixes that no clean bay has, and the answer comes out under 2003.
  • Forgetting the final +1. When highest itself is clean, as 250 is, it belongs in the clean total; omitting it flags one bay too many.
  • Letting the falling factorial go negative. With ten digits already spent the pool reaches zero, and the product must be 0 rather than a negative product of what comes after.

Variants