1069HardBacktrackingBit Manipulation

The Next Number Where Every Digit Counts Itself

Tracked in this browser only

Trains the technique from

LeetCode 3646Next Special Palindrome Number

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 whole number is self-counting when it reads the same backwards as forwards and, for every digit it uses, that digit appears exactly as many times as the digit itself. So a 4 may only appear in a number holding exactly four of them, and a 0 can never appear at all, since it would have to appear no times.

Return the smallest self-counting number strictly above n.

Examples

Example 1

Input: n = 0
Output: 1

A single `1` is self-counting, since it reads the same both ways and the digit one appears once.

Example 2

Input: n = 1
Output: 22

Nothing between two and twenty-one works, since any such number either fails to read the same backwards or holds a digit the wrong number of times. Two twos do both.

Example 3

Input: n = 45
Output: 212

No two-digit number above forty-five is self-counting, so the answer has three digits: one `1` in the middle with a `2` on either side.

Constraints

0 <= n <= 10^15

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

Java

public long specialPalindrome(long n)

The intended approach

Time O(1) in the size of the input, bounded by the arrangements of the digit collections.Space O(1).

Do not hunt upward from `n`; build the self-counting numbers instead, since there are remarkably few of them. Which digits a self-counting number uses settles almost everything. A digit `d` appears `d` times, so its count is odd exactly when the digit is odd. Reading the same both ways means at most one digit can have an odd count, the one sitting in the middle. So the digits used are some collection of the even digits together with at most one odd digit, and the number's length is those digits added up. For such a collection, half the number is settled by taking half of each even digit's count and half of the odd digit's count rounded down, with the odd digit itself in the middle. Every distinct arrangement of that half gives one self-counting number, and mirroring it gives the rest. There are only sixteen collections of even digits and six choices for the odd one, so run through the possible lengths in increasing order, build every self-counting number of that length, and take the smallest above `n`. Stopping at the first length that yields one keeps the arrangements few.

Pythonentry point: special_palindrome

def special_palindrome(n):
    evens = [2, 4, 6, 8]
    odds = [1, 3, 5, 7, 9]
    groups = {}
    for mask in range(16):
        base = []
        for k in range(4):
            if mask >> k & 1:
                base.append(evens[k])
        picks = [None]
        for d in odds:
            picks.append(d)
        for middle in picks:
            chosen = list(base)
            if middle is not None:
                chosen.append(middle)
            if not chosen:
                continue
            length = 0
            for d in chosen:
                length += d
            groups.setdefault(length, []).append((chosen, middle))
    for length in sorted(groups):
        found = None
        for chosen, middle in groups[length]:
            counts = {}
            for d in chosen:
                if d // 2:
                    counts[d] = d // 2
            digits = sorted(counts)
            acc = []
            want = 0
            for d in digits:
                want += counts[d]
            halves = []
            def walk():
                if len(acc) == want:
                    halves.append("".join(acc))
                    return
                for d in digits:
                    if counts[d]:
                        counts[d] -= 1
                        acc.append(str(d))
                        walk()
                        acc.pop()
                        counts[d] += 1
            walk()
            tail = str(middle) if middle is not None else ""
            for left in halves:
                value = int(left + tail + left[::-1])
                if value > n and (found is None or value < found):
                    found = value
        if found is not None:
            return found
    return -1

The obvious version

Count upward from one past `n`, and for each number test it directly: it must read the same backwards, and tallying its digits, each digit's tally must equal the digit. Return the first number that passes. Costs the gap up to the answer rather than a build from the digit collections.

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_special_palindrome(n):
    def counts_itself(value):
        text = str(value)
        if text != text[::-1]:
            return False
        tally = {}
        for ch in text:
            tally[ch] = tally.get(ch, 0) + 1
        for ch in tally:
            if int(ch) != tally[ch]:
                return False
        return True
    value = n + 1
    while True:
        if counts_itself(value):
            return value
        value += 1

How this problem was checked

Reference solution executed against 18 test cases — 18 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