0898HardMathDynamic Programming

Serials With No Digit Twice

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.

Serials are stamped as plain whole numbers with no leading zeros.

A serial is clean when no digit appears in it more than once.

Given n, return how many clean serials there are from 1 up to n inclusive.

Examples

Example 1

Input: n = 4321
Output: 2434

Every serial of one, two or three digits with no repeat counts, which is 9 plus 81 plus 648, and then the four-digit serials up to 4321 with no repeat add a further 1080.

Example 2

Input: n = 101
Output: 90

The nine single-digit serials are all clean, and of the ninety two-digit serials only the nine doubled ones are not. Neither 100 nor 101 is clean, so the count stops at 90.

Example 3

Input: n = 9
Output: 9

A single digit cannot repeat, so all nine serials are clean.

Constraints

1 <= n <= 2 * 10^9

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_special_numbers(n: int) -> int:

Java

public int countSpecialNumbers(int n)

The intended approach

Time O(d^2) for the d digits of n, with a falling product worked out per position.Space O(1): a fixed set of ten digit flags.

Serials shorter than `n` are free of any upper bound, so they can be counted outright: a serial of length `L` has nine choices for its leading digit, then nine, eight and so on for the rest, since each position must avoid every digit already used. Adding that over every length below `n`'s handles all of them at once. Serials of `n`'s own length need the bound. Walk `n`'s digits left to right holding the set of digits already committed to. At each position, any unused digit strictly below `n`'s digit there fixes a serial that is already smaller than `n`, and the positions after it may then be filled with any arrangement of the digits still unused, which is a falling product. Add those, then commit `n`'s own digit and carry on; if that digit was already used, no longer prefix can match `n` and the walk stops. Reaching the end without stopping means `n` itself is clean and counts too.

Pythonentry point: count_special_numbers

def count_special_numbers(n):
    def falling(top, take):
        out = 1
        for step in range(take):
            out *= top - step
        return out

    digits = []
    rest = n
    while rest > 0:
        digits.append(rest % 10)
        rest //= 10
    digits.reverse()
    length = len(digits)
    total = 0
    for shorter in range(1, length):
        total += 9 * falling(9, shorter - 1)
    used = [False] * 10
    stopped = False
    for at in range(length):
        low = 1 if at == 0 else 0
        for d in range(low, digits[at]):
            if used[d]:
                continue
            total += falling(10 - at - 1, length - at - 1)
        if used[digits[at]]:
            stopped = True
            break
        used[digits[at]] = True
    if not stopped:
        total += 1
    return total

The obvious version

Build the serials digit by digit instead of counting them. A position is described by how far along it is, which digits are spent, whether the prefix still matches `n`, and whether any non-zero digit has been placed yet; the count for a position is remembered so each one is worked out once. Enumerates the construction rather than reasoning about arrangements.

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_special_numbers(n):
    digits = [int(ch) for ch in str(n)]
    length = len(digits)
    memo = {}

    def walk(at, spent, tight, started):
        if at == length:
            return 1 if started else 0
        key = (at, spent, tight, started)
        if key in memo:
            return memo[key]
        top = digits[at] if tight else 9
        total = 0
        for d in range(top + 1):
            if not started and d == 0:
                total += walk(at + 1, spent, tight and d == top, False)
                continue
            if spent >> d & 1:
                continue
            total += walk(at + 1, spent | (1 << d), tight and d == top, True)
        memo[key] = total
        return total

    return walk(0, 0, True, False)

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