</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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 at most 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.

Digit and Number: four problems solved by arithmetic, not iteration

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.


Core 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. Checks worth running: n = 1, 3, 9, 10, 11, 15, 189, 190 give 1, 3, 9, 1, 0, 2, 9, 1. Position 189 is the last digit of 99 and 190 is the first digit of 100.

2. Five candidates, not a search

The nearest different palindrome to a d-digit number is always one of at most five values:

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

Mirroring the first half produces the nearest palindrome of the same length, and +1 or -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 (answer 999) and 99 (answer 101), where no same-length palindrome is closest. For 1000 the prefix-1 candidate is 99, not 990, and it is far away: the 99...9 boundary is what covers the shrink. For 999 the mirrors are 989, 999 (dropped because it equals n) and 1001, and 1001 wins.

The brute force that scans outward from n costs O(d * 10^(d/2)), because palindromes are about 10^(d/2) apart and each check is O(d). That is already hopeless for an 18-digit n.

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, every part is the value 0 and a trivial split such as [0, n-1] 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 fixes the width every part must have, so it bounds how far the first two parts may extend.

The three parts must be non-empty, so the middle part needs at least one element (i + 1 < j). Arrays shorter than 3 are outside the problem's constraint. Both special cases (not divisible, and all zeros) are decided before any alignment.


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

n = 11

Nth Digit worked example: the 11th digit is 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. After subtracting the 9 one-digit numbers, n = 2. 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

  • Offsets into variable-width records. Finding which group a position falls in by subtracting whole groups is the same shape as the band arithmetic.
  • XOR cancellation. XOR parity (as in RAID 5) relies on the same fact that a value XORed with itself is zero, so one missing item can be recovered from the rest.
  • Digit and string checks. Palindrome and digit-pattern checks are common in input validation.

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 up to five candidates from the mirrored prefix and the two length-changing extremes.
Pattern: bounded candidate generation. Target: O(d) in the digit count d, against O(d * 10^(d/2)) for scanning outward.

Single Number III

The two values appearing once among pairs. XOR everything, isolate the lowest set bit with mask = x & -x, and partition into two independent XOR problems. For [-5, 3], x = -8 and mask = 8.
Pattern: XOR partition on a differing bit. Target: O(n) time, O(1) space.

Three Equal Parts

Split a binary array into three non-empty 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 (answer 999) and 99 (answer 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. Return a split with a non-empty middle, such as [0, n-1].
  • Ignoring trailing zeros when aligning the three parts, which is what fixes the width of each part.
  • Negating the minimum integer. x & -x is safe in Python, but in C++ and Java x = INT_MIN overflows on -x; widen to 64 bits first.

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, with the INT_MIN caveat in C++ and Java.
  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.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.