Digit and Number Math

What is this?

Each of these looks like it needs a loop over a huge range and does not. The n-th digit of the infinite sequence 123456789101112… is found by subtracting whole bands of equal-length numbers. The nearest palindrome is one of exactly five candidates. Two unique numbers in an array separate on a single bit. And a binary array splits into three equal values only if its count of ones divides by three.

💡 Fun fact: Single Number III — two numbers appear once, all others twice — turns an apparently harder problem into two copies of an easier one. XOR everything: the pairs cancel, leaving a ^ b. That value is non-zero, so it has at least one set bit, and any set bit is a position where a and b differ. Isolate the lowest with x & -x, partition the whole array by that bit, and XOR each half separately. Each half contains exactly one of the unique numbers and pairs of everything else. Two passes, O(1) space, and the entire trick is that a differing bit is a perfect classifier.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: count in bands, bits or candidates rather than one at a time. Each of these replaces an unbounded loop with a fixed amount of arithmetic.

1. Bands of equal length

length, count, start = 1, 9, 1                   # 9 one-digit numbers starting at 1
while n > length * count:
    n -= length * count
    length += 1; count *= 10; start *= 10        # 90 two-digit, 900 three-digit, …
start += (n - 1) // length                       # which number in this band
return int(str(start)[(n - 1) % length])         # which digit inside it

The loop runs at most ten times for any 32-bit n. Both - 1s are the same off-by-one correction, converting a 1-based position into a 0-based offset, and both are needed — dropping either gives an answer that is correct for most inputs and wrong on every band boundary.

2. Five candidates, not a search

The nearest palindrome to an n-digit number is always one of:

cands = {10**(n-1) - 1,                          # 99…9   (one digit shorter)
         10**n + 1}                              # 10…01  (one digit longer)
prefix = int(s[:(n+1)//2])
for d in (-1, 0, 1):                             # mirror prefix−1, prefix, prefix+1
    p = str(prefix + d)
    cands.add(int(p + p[-2::-1] if n % 2 else p + p[::-1]))
cands.discard(int(s))                            # must be a DIFFERENT number

Mirroring the first half is what produces the nearest palindrome of the same length, and ±1 on the prefix covers the cases where the mirror lands on the wrong side of the input. The two length-changing candidates handle 1000 → 999 and 99 → 101, where no same-length palindrome is closest.

Ties go to the smaller number, which min(cands, key=lambda x: (abs(x - L), x)) gives directly.

3. Count first, then align

Three Equal Parts asks for a split of a binary array into three parts with equal value — leading zeros ignored, so the parts may differ in length.

If the total count of ones is not divisible by three, it is impossible. If it is zero, any split works. Otherwise each part holds exactly k = ones / 3 ones, which pins down where each part's first 1 sits. From there, walk all three forward together and require the digits to match; the number of trailing zeros after the last 1 bounds how far the first two parts may extend.

Both special cases — not divisible, and all zeros — are decided before any alignment, and both appear in the sample inputs.

4. A 30-second worked example (nth digit)

n = 11

band 1:  9 numbers × 1 digit  =  9   digits, covering positions 1–9
         11 > 9  → n = 11 − 9 = 2,  now length = 2, start = 10

band 2:  90 numbers × 2 digits = 180 digits
         2 ≤ 180  → stop here

which number:  start + (2 − 1) // 2  =  10 + 0  =  10
which digit:   (2 − 1) % 2  =  1     →  str(10)[1]  =  '0'

answer: 0

The sequence reads 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 …, and position 11 is indeed the 0 inside 10. Both − 1s are visible here: position 2 within the band is the second digit, which is offset 1 — and using n directly instead would return '1', the first digit of 11.

5. Where you'll actually meet this

• Pagination and offsets. Locating item n in variable-length records is the band arithmetic exactly.
• Error detection. XOR-based identification of an odd item out is how checksums and RAID parity work.
• Number formatting and validation. Palindrome and digit-pattern checks appear in ID and reference generation.
• Binary data partitioning. Splitting a bit stream into equal-value segments is a real framing problem.
• Compression and encoding. Digit-band counting underlies variable-length integer encodings.

6. Problems in this chapter

▶ Nth Digit

The n-th digit of the concatenated positive integers. Subtract whole bands of equal-length numbers, then index within one.
Pattern: counting by digit bands. Target: O(log n) time, O(1) space.

▶ Find the Closest Palindrome

Nearest palindrome that is a different number, smaller on a tie. Generate five candidates from the mirrored prefix and the two length-changing extremes.
Pattern: bounded candidate generation. Target: O(n) in the digit count.

▶ Single Number III

The two values appearing once among pairs. XOR everything, isolate the lowest differing bit, and partition into two independent XOR problems.
Pattern: XOR partition on a differing bit. Target: O(n) time, O(1) space.

▶ Three Equal Parts

Split a binary array into three parts of equal value. Require the count of ones to divide by three, then align each part's first 1 and match forward.
Pattern: counting + alignment. Target: O(n) time, O(1) extra space.

7. Common pitfalls 🚫

• Dropping either − 1 in the digit indexing, which fails on band boundaries.
• Iterating outward from the input to find the nearest palindrome, which is unbounded.
• Forgetting the length-changing candidates. 1000 → 999 and 99 → 101 are not same-length mirrors.
• Returning the input itself as its own nearest palindrome. It must be different.
• Using a bit that is not set in a ^ b to partition. Any set bit works; an unset one puts both numbers on the same side.
• Missing the all-zeros case in Three Equal Parts, which is valid and splits anywhere.
• Ignoring trailing zeros when aligning the three parts, which is what bounds the first two.

8. Key takeaways

1. Count in bands. Whole groups of equal length collapse an unbounded loop into ten iterations.
2. When the answer space is provably tiny, generate it. Five candidates beat any search.
3. A differing bit is a perfect classifier, which turns one hard problem into two easy ones.
4. x & -x isolates the lowest set bit — worth knowing cold.
5. Divisibility decides feasibility before any construction begins.
6. Off-by-ones live at boundaries. Test the first and last element of every band.
7. Why interviewers like it: each has an O(1)-space arithmetic answer that cannot be brute-forced, so it is visible immediately whether you know it.

Order: Nth Digit → Find the Closest Palindrome → Single Number III → Three Equal Parts.