Digit Manipulation

Digit Manipulation

A surprisingly wide class of problems reduce to operations on individual digits: reversing an integer, checking whether a number reads the same forwards and backwards, detecting cycles in digit-sum sequences, or computing a digital root without any loops at all. The mechanics are simple, but the edge cases, namely overflow, negative numbers, and trailing zeros, trip up solutions that skip careful thought.

Extracting and Consuming Digits

The two fundamental operations are extracting the last digit with n % 10 and removing the last digit with n //= 10. Repeating these in a loop processes digits from least significant to most significant. To build a new number from those digits in the same order you encounter them, use the accumulator pattern: result = result * 10 + digit. Each iteration shifts the already-accumulated digits one place left and appends the new one at the units position.

def digit_sum(n: int) -> int:
    n = abs(n)
    total = 0
    while n:
        total += n % 10
        n //= 10
    return total

Reversing an Integer

Reversing an integer is the direct application of the accumulator pattern. The tricky part is overflow: the reversed number might not fit in a 32-bit signed integer even if the original did. In Python, integers are arbitrary precision so there is no hardware overflow, but LeetCode 7. Reverse Integer asks you to return 0 if the result falls outside $[-2^{31}, 2^{31} - 1]$.

def reverse_integer(x: int) -> int:
    sign = -1 if x < 0 else 1
    x = abs(x)
    rev = 0
    while x:
        rev = rev * 10 + x % 10
        x //= 10
    rev *= sign
    return rev if -(2**31) <= rev <= 2**31 - 1 else 0

Walked example, reversing 1234:

Iteration 1: digit = 4, rev = 0×10 + 4 = 4, x = 123. Iteration 2: digit = 3, rev = 4×10 + 3 = 43, x = 12. Iteration 3: digit = 2, rev = 43×10 + 2 = 432, x = 1. Iteration 4: digit = 1, rev = 432×10 + 1 = 4321, x = 0.

Loop ends. Result is 4321, well within bounds.

Overflow case, reversing 1000000003:

Full reversal gives 3000000001, which exceeds $2^{31} - 1$ = 2147483647, so the function returns 0. Note that a number ending in one or more zeros will lose those leading zeros after reversal (e.g., 120 becomes 021 = 21), which is handled naturally by the loop since the leading zeros never get accumulated.

Palindrome Number Check

LeetCode 9 asks whether a number is a palindrome, meaning it equals its own reversal. The naive approach reverses the entire number and compares, but that risks overflow and handles trailing-zero inputs awkwardly. The cleaner approach reverses only the second half of the digits and compares against the first half. We stop when the reversed portion grows at least as large as the remaining original number.

def is_palindrome(x: int) -> bool:
    # Negative numbers and numbers ending in 0 (except 0 itself) are never palindromes
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    rev_half = 0
    while x > rev_half:
        rev_half = rev_half * 10 + x % 10
        x //= 10
    # Even-length: x == rev_half exactly
    # Odd-length: middle digit sits in rev_half, discard it with // 10
    return x == rev_half or x == rev_half // 10

Walked example, 1221 (even length):

Start: x=1221, rev_half=0. Step 1: rev_half = 1, x = 122. Still x > rev_half, continue. Step 2: rev_half = 12, x = 12. Now x == rev_half, stop. Return 12 == 12: True.

Walked example, 12321 (odd length):

Start: x=12321, rev_half=0. Step 1: rev_half=1, x=1232. Step 2: rev_half=12, x=123. Step 3: rev_half=123, x=12. Now x < rev_half, stop. Return 12 == 123 // 10 = 12: True. The middle digit 3 is discarded by the integer division.

Non-palindrome, 12345:

After the loop, x=12 and rev_half=543. Neither 12 == 543 nor 12 == 54, so return False.

Happy Number: Cycle Detection on Digit Sums

A happy number (LeetCode 202. Happy Number) is one where repeatedly replacing the number with the sum of squares of its digits eventually reaches 1. Unhappy numbers cycle forever. Use Floyd's slow/fast pointer cycle detection on the sequence of digit-square sums.

def is_happy(n: int) -> bool:
    def digit_square_sum(num: int) -> int:
        total = 0
        while num:
            d = num % 10
            total += d * d
            num //= 10
        return total

    slow, fast = n, digit_square_sum(n)
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
    return fast == 1

The slow pointer advances one step at a time while the fast pointer advances two. If there is a cycle (unhappy number), the two pointers will eventually meet before reaching 1. If the sequence terminates at 1 (happy number), fast == 1 triggers the loop exit. You could also short-circuit on the value 4, since every unhappy number's cycle passes through 4, but the Floyd approach is more general.

Digital Root: $O(1)$ Formula

The digital root (LeetCode 258. Add Digits) is the value you get by repeatedly summing digits until you reach a single digit. A loop works but is unnecessary, since the result follows directly from modular arithmetic. Any integer n is congruent to the sum of its digits modulo 9, so the iterative process converges to n mod 9. The only special case is that a nonzero multiple of 9 should yield 9, not 0.

def add_digits(n: int) -> int:
    if n == 0:
        return 0
    return 1 + (n - 1) % 9

For n=9: (9-1)%9 = 8, result = 9. For n=18: (18-1)%9 = 8, result = 9. For n=10: (10-1)%9 = 0, result = 1. All correct with no loops required.

Maximum Swap

LeetCode 670. Maximum Swap asks for the largest number obtainable by swapping exactly two digits at most once. The key insight: for each digit 0 through 9 record the rightmost index where it appears, then scan left-to-right and for the current position check if any larger digit appears to its right. Swap with the rightmost occurrence of the largest such digit to maximize the result.

def maximum_swap(num: int) -> int:
    digits = list(str(num))
    last = {int(d): i for i, d in enumerate(digits)}  # rightmost index of each digit
    for i, d in enumerate(digits):
        for larger in range(9, int(d), -1):  # check 9 down to d+1
            if last.get(larger, -1) > i:
                j = last[larger]
                digits[i], digits[j] = digits[j], digits[i]
                return int("".join(digits))
    return num  # already the largest arrangement

Walked example, 2736:

Rightmost indices: {2:0, 7:1, 3:2, 6:3}. Scan from left: at index 0 digit is 2, check 9..3: digit 7 exists at index 1 and digit 3 at index 2 and digit 6 at index 3. The largest is 7 at index 1. Swap positions 0 and 1: result 7236. This is the maximum achievable with one swap.

Base Conversion

Problems like LeetCode 405. Convert a Number to Hexadecimal and LeetCode 504. Base 7 follow the same template: repeatedly divide by the base and collect remainders. The remainders, read in reverse order, form the digits of the target representation. For hexadecimal, map remainders 10 through 15 to letters a through f. Negative numbers in hex use two's-complement representation.

def to_base7(num: int) -> str:
    if num == 0:
        return "0"
    sign = "-" if num < 0 else ""
    num = abs(num)
    digits = []
    while num:
        digits.append(str(num % 7))
        num //= 7
    return sign + "".join(reversed(digits))

def to_hex(num: int) -> str:
    if num == 0:
        return "0"
    if num < 0:
        num += 2**32  # two's complement for negative numbers
    hex_chars = "0123456789abcdef"
    digits = []
    while num:
        digits.append(hex_chars[num % 16])
        num //= 16
    return "".join(reversed(digits))

The pattern generalizes to any base. The only wrinkle is how negatives are handled: base 7 uses a minus sign, but hexadecimal uses two's complement (adding $2^{32}$) to match hardware behavior.

Closest Palindrome

LeetCode 564. Find the Closest Palindrome asks for the nearest palindrome to a given number (as a string), excluding the number itself. The strategy is to generate a small set of candidates by mirroring the first half of the input, then pick the closest. The candidates are:

1. Mirror the first half as-is.
2. Mirror the first half incremented by 1.
3. Mirror the first half decremented by 1.
4. Edge case: all 9s with one fewer digit (e.g., 999 for a 4-digit input, which is $10^{d-1} - 1$).
5. Edge case: 10...01 with one more digit (e.g., 10001 for a 4-digit input, which is $10^d + 1$).

def nearest_palindrome(n_str: str) -> str:
    n = int(n_str)
    length = len(n_str)
    half = int(n_str[:(length + 1) // 2])  # first half (includes middle for odd length)

    def mirror(h: int) -> int:
        s = str(h)
        return int(s + s[-2::-1] if length % 2 else s + s[::-1])

    candidates = set()
    for delta in (-1, 0, 1):
        candidates.add(mirror(half + delta))
    candidates.add(10 ** (length - 1) - 1)  # e.g., 999
    candidates.add(10 ** length + 1)          # e.g., 10001
    candidates.discard(n)  # must differ from input

    return str(min(candidates, key=lambda c: (abs(c - n), c)))

The min tiebreaker picks the smaller candidate when two are equidistant. The candidate set is always at most 5 elements, so the whole algorithm runs in $O(d)$ time.

Reordered Power of 2

LeetCode 869. Reordered Power of 2: given an integer n, can you reorder its digits (no leading zeros) to form a power of 2? There are only 30 powers of 2 below $10^{9}$ (the constraint), so precompute the sorted digit signature of each and compare against the input's sorted digits.

def reordered_power_of2(n: int) -> bool:
    target = sorted(str(n))
    return any(sorted(str(1 << i)) == target for i in range(31))

Sorting the digits is a counting-sort-style fingerprint. Two numbers are digit-rearrangements of each other if and only if their sorted digit strings match. The outer loop is $O(30)$ and sorting each candidate is $O(d)$, so the total cost is $O(d)$, effectively constant.

Add to Array-Form of Integer

LeetCode 989. Add to Array-Form of Integer represents an integer as an array of its digits (most significant first) and asks you to add a plain integer k to it. Simulate grade-school addition from the least significant digit, carrying over as you go.

def add_to_array_form(num: list[int], k: int) -> list[int]:
    i = len(num) - 1
    carry = k
    while i >= 0 or carry:
        if i >= 0:
            carry += num[i]
        if i >= 0:
            num[i] = carry % 10
        else:
            num.insert(0, carry % 10)
        carry //= 10
        i -= 1
    return num

Walked example, num = [2, 7, 4], k = 181:

Start from right: 4 + 181 = 185 → digit 5, carry 18. Next: 7 + 18 = 25 → digit 5, carry 2. Next: 2 + 2 = 4 → digit 4, carry 0. Result: [4, 5, 5]. This is 274 + 181 = 455, confirmed.

The approach treats k itself as the carry, which elegantly unifies the case where k has more digits than the array. No string conversion or big-integer library is needed.

Complexity Summary

All of these algorithms run in $O(d)$ time where d is the number of digits, which is $O(\log n)$ in terms of numeric value. Space is $O(1)$ for integer reversal, palindrome check, and digital root. The happy number check requires $O(\log n)$ per step; the sequence is guaranteed to enter a cycle or reach 1 within $O(\log n)$ steps, giving $O(\log^2 n)$ overall, negligible in practice for the integer sizes encountered on LeetCode.

Recognizing this pattern

You're probably looking at digit manipulation when:

• The problem asks you to reverse an integer, check if it's a palindrome number, or compute a happy number.
• You need the sum, product, or count of digits, possibly modulo something.
• You're asked for the next or previous integer with the same digit multiset, or the next greater number with digits permuted.
• The natural temptation is to convert to a string, but the constraint says "without converting to a string" or you want O(1) space.

Common templates:

• Mod-10 / div-10 reverse loop: peel digits off the right while building the reversed value. Example: Reverse Integer.
• Half-reverse palindrome check: reverse only the lower half and compare to the upper. Example: Palindrome Number.
• Digit-sum iteration to fixed point: repeatedly replace n with a function of its digits. Example: Happy Number.
• Next permutation on digits: find pivot, swap, reverse suffix. Example: Next Greater Element III.