⌘K

Digits and Number Manipulation

EditorialUpdated Oct 31, 2026

The loop everyone writes first

Reverse Integer asks for the digits of a 32-bit integer in reverse order, or 0 when the reverse doesn't fit in 32 bits. Here's the loop almost everyone writes first, run on 123 and on 1,534,236,469:

#include <bits/stdc++.h>
using namespace std;

int reverse(int x) {                   // the loop everyone writes first
    int result = 0;
    while (x != 0) {
        result = result * 10 + x % 10;
        x /= 10;
    }
    return result;
}

int main() {
    printf("%d %d\n", reverse(123), reverse(1534236469));
}

// 321 1056389759

def reverse(x):                       # the loop everyone writes first
    sign = -1 if x < 0 else 1
    x = abs(x)
    result = 0
    while x != 0:
        result = result * 10 + x % 10
        x //= 10
    return sign * result


print(reverse(123), reverse(1534236469))

# 321 9646324351

public class Main {
    static int reverse(int x) {        // the loop everyone writes first
        int result = 0;
        while (x != 0) {
            result = result * 10 + x % 10;
            x /= 10;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(reverse(123) + " " + reverse(1534236469));
    }
}

// 321 1056389759

function reverse(x) {                  // the loop everyone writes first
    let result = 0;
    while (x !== 0) {
        result = result * 10 + x % 10;
        x = Math.trunc(x / 10);
    }
    return result;
}

console.log(reverse(123), reverse(1534236469));

// 321 9646324351

On 123 all four agree: 321. On 1,534,236,469 they don't. C++ and Java printed 1,056,389,759: the true reverse, 9,646,324,351, is bigger than the largest 32-bit integer, 2,147,483,647, so the int wrapped around past 2³². In Java that wrap is defined; in C++ it's undefined behaviour, so not even that number is promised. Python and JavaScript printed 9,646,324,351, because their numbers don't stop at 32 bits. The answer the problem wants is 0, and none of them gave it.

Every problem in this lesson is that loop. % 10 takes the last digit off, / 10 drops it, and × 10 + digit puts one on. What changes is one decision: the sign, the overflow, the base, or a carry. This lesson takes them in turn, then multiplies numbers too long for any integer type, digit by digit.

Two dashed panels. Left, take 4837 apart, in blue: four rows of digit tiles, 4837, 483, 48 and 4, each with its last tile in orange and a pill beside it reading % 10 = 7, 3, 8 and 4, and a down arrow marked / 10 between one row and the next. Right, build it back, in green: four rows, 0 × 10 + 7, 7 × 10 + 3, 73 × 10 + 8 and 738 × 10 + 4, each with its result as tiles, 7, 73, 738 and 7384, the newest digit in orange. Focal line: % 10 takes a digit off, × 10 + d puts one on. Title: peel off the last digit.

Taking a number apart

n % 10 is the last digit of n, and n / 10 (whole-number division) is n without it. Repeat until nothing is left and the digits come off right to left, one per pass:

#include <bits/stdc++.h>
using namespace std;

vector<int> digitsOff(long long n) {   // the digits of n >= 0, last one first
    vector<int> out;
    do {
        out.push_back(n % 10);         // the last digit
        n /= 10;                       // drop it
    } while (n != 0);
    return out;
}

int main() {
    for (long long n : {4837LL, 0LL, 1000000LL}) {
        vector<int> d = digitsOff(n);
        int sum = 0;
        printf("%lld:", n);
        for (int x : d) {
            printf(" %d", x);
            sum += x;
        }
        printf(" off the right, count %zu, sum %d\n", d.size(), sum);
    }
}

// 4837: 7 3 8 4 off the right, count 4, sum 22
// 0: 0 off the right, count 1, sum 0
// 1000000: 0 0 0 0 0 0 1 off the right, count 7, sum 1

def digits_off(n):                    # the digits of n >= 0, last one first
    out = []
    while True:
        out.append(n % 10)            # the last digit
        n //= 10                      # drop it
        if n == 0:
            return out


for n in (4837, 0, 1000000):
    d = digits_off(n)
    print(f"{n}: {' '.join(map(str, d))} off the right, count {len(d)}, sum {sum(d)}")

# 4837: 7 3 8 4 off the right, count 4, sum 22
# 0: 0 off the right, count 1, sum 0
# 1000000: 0 0 0 0 0 0 1 off the right, count 7, sum 1

import java.util.*;

public class Main {
    static List<Integer> digitsOff(long n) {   // the digits of n >= 0, last one first
        List<Integer> out = new ArrayList<>();
        do {
            out.add((int) (n % 10));            // the last digit
            n /= 10;                            // drop it
        } while (n != 0);
        return out;
    }

    public static void main(String[] args) {
        for (long n : new long[]{4837, 0, 1000000}) {
            List<Integer> d = digitsOff(n);
            int sum = 0;
            StringBuilder line = new StringBuilder(n + ":");
            for (int x : d) {
                line.append(" ").append(x);
                sum += x;
            }
            System.out.println(line + " off the right, count " + d.size() + ", sum " + sum);
        }
    }
}

// 4837: 7 3 8 4 off the right, count 4, sum 22
// 0: 0 off the right, count 1, sum 0
// 1000000: 0 0 0 0 0 0 1 off the right, count 7, sum 1

function digitsOff(n) {                // the digits of n >= 0, last one first
    const out = [];
    do {
        out.push(n % 10);              // the last digit
        n = Math.floor(n / 10);        // drop it
    } while (n !== 0);
    return out;
}

for (const n of [4837, 0, 1000000]) {
    const d = digitsOff(n);
    const sum = d.reduce((a, b) => a + b, 0);
    console.log(`${n}: ${d.join(" ")} off the right, count ${d.length}, sum ${sum}`);
}

// 4837: 7 3 8 4 off the right, count 4, sum 22
// 0: 0 off the right, count 1, sum 0
// 1000000: 0 0 0 0 0 0 1 off the right, count 7, sum 1

4,837 gave 7, 3, 8 and 4, in four passes. A number with d digits takes d passes, and n has ⌊log₁₀ n⌋ + 1 digits, so the loop is O(log n): at most 10 passes for a 32-bit number and 19 for a 64-bit one.

The loop divides first and tests after, so 0 gets one pass and one digit. Testing first (while n > 0) never enters the loop for 0 and counts no digits, the most common slip in Count Digits of a Number.

Armstrong numbers use the loop to count the digits, then add up each digit raised to that count. 153 is one: 1³ + 5³ + 3³ = 153. Checking every number below a million:

#include <bits/stdc++.h>
using namespace std;

bool isArmstrong(long long n) {        // the sum of its digits, each to the power of how many there are
    vector<int> digits;
    long long m = n;
    do {
        digits.push_back(m % 10);
        m /= 10;
    } while (m != 0);
    long long total = 0;
    for (int d : digits) {
        long long power = 1;
        for (size_t k = 0; k < digits.size(); k++) power *= d;   // whole numbers only, no pow()
        total += power;
    }
    return total == n;
}

int main() {
    vector<long long> found;
    for (long long n = 1; n < 1000000; n++)
        if (isArmstrong(n)) found.push_back(n);
    printf("%zu below 1,000,000:", found.size());
    for (long long n : found) printf(" %lld", n);
    printf("\n");
}

// 20 below 1,000,000: 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834

def is_armstrong(n):                  # the sum of its digits, each to the power of how many there are
    digits = []
    m = n
    while True:
        digits.append(m % 10)
        m //= 10
        if m == 0:
            break
    k = len(digits)
    return sum(d ** k for d in digits) == n


found = [n for n in range(1, 1000000) if is_armstrong(n)]
print(f"{len(found)} below 1,000,000:", " ".join(map(str, found)))

# 20 below 1,000,000: 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834

import java.util.*;

public class Main {
    static boolean isArmstrong(long n) {   // the sum of its digits, each to the power of how many there are
        List<Integer> digits = new ArrayList<>();
        long m = n;
        do {
            digits.add((int) (m % 10));
            m /= 10;
        } while (m != 0);
        long total = 0;
        for (int d : digits) {
            long power = 1;
            for (int k = 0; k < digits.size(); k++) power *= d;   // whole numbers only, no Math.pow
            total += power;
        }
        return total == n;
    }

    public static void main(String[] args) {
        StringBuilder line = new StringBuilder();
        int count = 0;
        for (long n = 1; n < 1000000; n++)
            if (isArmstrong(n)) {
                line.append(" ").append(n);
                count++;
            }
        System.out.println(count + " below 1,000,000:" + line);
    }
}

// 20 below 1,000,000: 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834

function isArmstrong(n) {              // the sum of its digits, each to the power of how many there are
    const digits = [];
    let m = n;
    do {
        digits.push(m % 10);
        m = Math.floor(m / 10);
    } while (m !== 0);
    let total = 0;
    for (const d of digits) {
        let power = 1;
        for (let k = 0; k < digits.length; k++) power *= d;   // whole numbers only, no Math.pow
        total += power;
    }
    return total === n;
}

const found = [];
for (let n = 1; n < 1000000; n++) if (isArmstrong(n)) found.push(n);
console.log(`${found.length} below 1,000,000: ${found.join(" ")}`);

// 20 below 1,000,000: 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834

There are 20 below a million, the largest 548,834. Each power is built by multiplying whole numbers, so no floating-point rounding is involved.

Negative numbers: each language rounds its own way

For a negative number the two operations disagree between languages. C++, Java and JavaScript round the quotient toward zero and give the remainder the dividend's sign; Python rounds down and gives it the divisor's sign:

#include <bits/stdc++.h>
using namespace std;

int main() {
    printf("-123 %% 10 = %d\n", -123 % 10);   // the remainder takes the dividend's sign
    printf("-123 / 10 = %d\n", -123 / 10);     // the quotient rounds toward zero
}

// -123 % 10 = -3
// -123 / 10 = -12

print("-123 % 10 =", -123 % 10)              # the remainder takes the divisor's sign
print("-123 // 10 =", -123 // 10)            # the quotient rounds down
print("int(-123 / 10) =", int(-123 / 10))    # true division, then toward zero

# -123 % 10 = 7
# -123 // 10 = -13
# int(-123 / 10) = -12

public class Main {
    public static void main(String[] args) {
        System.out.println("-123 % 10 = " + (-123 % 10));   // the remainder takes the dividend's sign
        System.out.println("-123 / 10 = " + (-123 / 10));   // the quotient rounds toward zero
        System.out.println("Math.abs(-2147483648) = " + Math.abs(-2147483648));
    }
}

// -123 % 10 = -3
// -123 / 10 = -12
// Math.abs(-2147483648) = -2147483648

console.log("-123 % 10 =", -123 % 10);                          // the dividend's sign
console.log("Math.trunc(-123 / 10) =", Math.trunc(-123 / 10));  // toward zero
console.log("Math.floor(-123 / 10) =", Math.floor(-123 / 10));  // down

// -123 % 10 = -3
// Math.trunc(-123 / 10) = -12
// Math.floor(-123 / 10) = -13

Language	−123 % 10	−123 divided by 10
C++	−3	−12 with `/` (toward zero)
Python	7	−13 with `//` (down), −12 with `int(-123 / 10)`
Java	−3	−12 with `/` (toward zero)
JavaScript	−3	−12 with `Math.trunc`, −13 with `Math.floor`

Both rules keep (n / 10) × 10 + n % 10 equal to n; they split n differently. So a digit loop ported from Java to Python finds 7 as the last digit of −123, and one ported the other way finds −3. The habit that works everywhere: take the sign off, work on the size, put the sign back.

Taking the sign off has a trap of its own in 32 bits: the smallest int, −2,147,483,648, has no positive partner. Java's Math.abs of it printed −2,147,483,648, still negative, and in C++ it's undefined behaviour. That's why the 32-bit reverse below keeps the sign in its digits instead.

Counting digits with logarithms

On paper n ≥ 1 has ⌊log₁₀ n⌋ + 1 digits, and without a log₁₀ at hand people write it as log(n) / log(10). Computed in a double, both go wrong:

#include <bits/stdc++.h>
using namespace std;

int countDigits(long long n) {         // the loop: always right
    int count = 0;
    do {
        count++;
        n /= 10;
    } while (n != 0);
    return count;
}

int main() {
    for (long long n : {1000LL, 999999999999999LL}) {
        int byLog10 = (int) floor(log10((double) n)) + 1;
        int byLn = (int) floor(log((double) n) / log(10.0)) + 1;
        printf("%lld: loop %d, log10 %d, log(n)/log(10) %d\n", n, countDigits(n), byLog10, byLn);
    }
}

// 1000: loop 4, log10 4, log(n)/log(10) 3
// 999999999999999: loop 15, log10 16, log(n)/log(10) 15

import math


def count_digits(n):                  # the loop: always right
    count = 0
    while True:
        count += 1
        n //= 10
        if n == 0:
            return count


for n in (1000, 999999999999999):
    by_log10 = math.floor(math.log10(n)) + 1
    by_ln = math.floor(math.log(n) / math.log(10)) + 1
    print(f"{n}: loop {count_digits(n)}, log10 {by_log10}, log(n)/log(10) {by_ln}")

# 1000: loop 4, log10 4, log(n)/log(10) 3
# 999999999999999: loop 15, log10 16, log(n)/log(10) 15

public class Main {
    static int countDigits(long n) {   // the loop: always right
        int count = 0;
        do {
            count++;
            n /= 10;
        } while (n != 0);
        return count;
    }

    public static void main(String[] args) {
        for (long n : new long[]{1000L, 999999999999999L}) {
            int byLog10 = (int) Math.floor(Math.log10(n)) + 1;
            int byLn = (int) Math.floor(Math.log(n) / Math.log(10)) + 1;
            System.out.println(n + ": loop " + countDigits(n) + ", log10 " + byLog10 + ", log(n)/log(10) " + byLn);
        }
    }
}

// 1000: loop 4, log10 4, log(n)/log(10) 3
// 999999999999999: loop 15, log10 16, log(n)/log(10) 15

function countDigits(n) {              // the loop: always right
    let count = 0;
    do {
        count++;
        n = Math.floor(n / 10);
    } while (n !== 0);
    return count;
}

for (const n of [1000, 999999999999999]) {
    const byLog10 = Math.floor(Math.log10(n)) + 1;
    const byLn = Math.floor(Math.log(n) / Math.log(10)) + 1;
    console.log(`${n}: loop ${countDigits(n)}, log10 ${byLog10}, log(n)/log(10) ${byLn}`);
}

// 1000: loop 4, log10 4, log(n)/log(10) 3
// 999999999999999: loop 15, log10 16, log(n)/log(10) 15

log(1,000) / log(10) came out just under 3, so the second formula said 1,000 has 3 digits. And log₁₀(999,999,999,999,999) rounded to exactly 15.0, though the number itself is stored exactly, so the first said 16 digits; it has 15. All four languages printed the same. The loop does at most 19 divisions for any 64-bit number and is always right: use it, or the length of the number written as a string.

Building a number back up

result × 10 + digit appends a digit: 48 × 10 + 3 = 483. Feeding it the digits in the order they come off reverses the number. Palindrome Number needs only half of that: reverse the back half and compare it with the front, which never overflows and never builds a string:

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(int x) {             // without a string, reversing only the back half
    if (x < 0 || (x % 10 == 0 && x != 0))
        return false;                  // a minus sign, or a last 0 the first digit can't match
    int half = 0;
    while (x > half) {
        half = half * 10 + x % 10;
        x /= 10;
    }
    return x == half || x == half / 10;   // an odd count leaves the middle digit in half
}

int main() {
    for (int x : {121, -121, 10, 1221, 12321, 0})
        printf("%d %s\n", x, isPalindrome(x) ? "yes" : "no");
}

// 121 yes
// -121 no
// 10 no
// 1221 yes
// 12321 yes
// 0 yes

def is_palindrome(x):                 # without a string, reversing only the back half
    if x < 0 or (x % 10 == 0 and x != 0):
        return False                  # a minus sign, or a last 0 the first digit can't match
    half = 0
    while x > half:
        half = half * 10 + x % 10
        x //= 10
    return x == half or x == half // 10   # an odd count leaves the middle digit in half


for x in (121, -121, 10, 1221, 12321, 0):
    print(x, "yes" if is_palindrome(x) else "no")

# 121 yes
# -121 no
# 10 no
# 1221 yes
# 12321 yes
# 0 yes

public class Main {
    static boolean isPalindrome(int x) {   // without a string, reversing only the back half
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;                  // a minus sign, or a last 0 the first digit can't match
        int half = 0;
        while (x > half) {
            half = half * 10 + x % 10;
            x /= 10;
        }
        return x == half || x == half / 10;   // an odd count leaves the middle digit in half
    }

    public static void main(String[] args) {
        for (int x : new int[]{121, -121, 10, 1221, 12321, 0})
            System.out.println(x + " " + (isPalindrome(x) ? "yes" : "no"));
    }
}

// 121 yes
// -121 no
// 10 no
// 1221 yes
// 12321 yes
// 0 yes

function isPalindrome(x) {             // without a string, reversing only the back half
    if (x < 0 || (x % 10 === 0 && x !== 0))
        return false;                  // a minus sign, or a last 0 the first digit can't match
    let half = 0;
    while (x > half) {
        half = half * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    return x === half || x === Math.floor(half / 10);   // an odd count leaves the middle digit in half
}

for (const x of [121, -121, 10, 1221, 12321, 0])
    console.log(x, isPalindrome(x) ? "yes" : "no");

// 121 yes
// -121 no
// 10 no
// 1221 yes
// 12321 yes
// 0 yes

The loop stops once the reversed half catches up with what's left: 1221 leaves 12 and 12. With an odd count the middle digit ends up on the reversed side (12321 leaves 12 and 123), so it's dropped with / 10 before comparing. A negative number can't be a palindrome, since the minus sign has no partner, and neither can a number ending in 0 other than 0 itself, so both return early.

Plus One gives a number as an array of digits and adds 1 the way you do on paper: from the right, a digit below 9 goes up by one and that's the end; a 9 becomes 0 and the 1 carries left; if every digit was 9, a new 1 goes in front:

#include <bits/stdc++.h>
using namespace std;

vector<int> plusOne(vector<int> digits) {   // the digits of a number, most significant first
    for (int i = digits.size() - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;               // no carry: done
            return digits;
        }
        digits[i] = 0;                 // 9 + 1: write 0, carry 1 left
    }
    digits.insert(digits.begin(), 1);  // every digit was 9
    return digits;
}

int main() {
    for (vector<int> d : vector<vector<int>>{{1, 2, 3}, {4, 3, 9, 9}, {9, 9, 9}}) {
        for (int x : d) printf("%d", x);
        printf(" -> ");
        for (int x : plusOne(d)) printf("%d", x);
        printf("\n");
    }
}

// 123 -> 124
// 4399 -> 4400
// 999 -> 1000

def plus_one(digits):                 # the digits of a number, most significant first
    digits = digits[:]                # keep the caller's list
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1            # no carry: done
            return digits
        digits[i] = 0                 # 9 + 1: write 0, carry 1 left
    return [1] + digits               # every digit was 9


for d in ([1, 2, 3], [4, 3, 9, 9], [9, 9, 9]):
    print("".join(map(str, d)), "->", "".join(map(str, plus_one(d))))

# 123 -> 124
# 4399 -> 4400
# 999 -> 1000

import java.util.*;

public class Main {
    static int[] plusOne(int[] digits) {   // the digits of a number, most significant first
        digits = digits.clone();           // keep the caller's array
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;               // no carry: done
                return digits;
            }
            digits[i] = 0;                 // 9 + 1: write 0, carry 1 left
        }
        int[] longer = new int[digits.length + 1];
        longer[0] = 1;                     // every digit was 9: 1 followed by zeros
        return longer;
    }

    static String joined(int[] digits) {
        StringBuilder s = new StringBuilder();
        for (int x : digits) s.append(x);
        return s.toString();
    }

    public static void main(String[] args) {
        for (int[] d : new int[][]{{1, 2, 3}, {4, 3, 9, 9}, {9, 9, 9}})
            System.out.println(joined(d) + " -> " + joined(plusOne(d)));
    }
}

// 123 -> 124
// 4399 -> 4400
// 999 -> 1000

function plusOne(digits) {             // the digits of a number, most significant first
    digits = digits.slice();           // keep the caller's array
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;               // no carry: done
            return digits;
        }
        digits[i] = 0;                 // 9 + 1: write 0, carry 1 left
    }
    return [1, ...digits];             // every digit was 9
}

for (const d of [[1, 2, 3], [4, 3, 9, 9], [9, 9, 9]])
    console.log(d.join(""), "->", plusOne(d).join(""));

// 123 -> 124
// 4399 -> 4400
// 999 -> 1000

It's O(n) in the number of digits, and it never turns the array into a number. The array can hold 100 digits, and no integer type holds that; Mistakes that cost an interview shows what happens when you try.

Reversing without overflow

A 32-bit int holds −2,147,483,648 to 2,147,483,647. The reverse has to be checked before result × 10 + digit runs: in C++ and Java the overflow has already happened by the time you could look at the result. Two comparisons are enough:

if result is above 214,748,364 (that's 2,147,483,647 / 10), result × 10 alone passes the limit;
if it equals 214,748,364, result × 10 is 2,147,483,640, and only a last digit above 7 pushes it over.

The negative side is the same with −214,748,364 and −8, because the smallest int ends in 8:

Three dashed bands. Green, result = 214,748,364: a blue tile 214,748,364, an arrow marked × 10 to a blue tile 2,147,483,640, an arrow marked + 0 to 7 to a green tile reading at most 2,147,483,647, and a tick. Red, result = 214,748,365: the tile 214,748,365, × 10 to a red tile 2,147,483,650, the words already past 2,147,483,647, and a cross. Below, a number line with a red dashed mark at the largest int, 2,147,483,647, a green dot at 214,748,364 × 10 with a green band from it up to the mark, and a red dot past the mark at 214,748,365 × 10. Focal line: compare result with 214,748,364 before × 10. Title: check before you multiply.

#include <bits/stdc++.h>
using namespace std;

int reverse(int x) {                   // 0 when the reverse doesn't fit in 32 bits
    int result = 0;
    while (x != 0) {
        int digit = x % 10;            // negative when x is: C++ keeps the dividend's sign
        x /= 10;
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) return 0;
        if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) return 0;
        result = result * 10 + digit;  // safe: checked before it could pass the limit
    }
    return result;
}

int main() {
    for (int x : {123, -123, 120, 1534236469, 1463847412, INT_MIN})
        printf("%d -> %d\n", x, reverse(x));
}

// 123 -> 321
// -123 -> -321
// 120 -> 21
// 1534236469 -> 0
// 1463847412 -> 2147483641
// -2147483648 -> 0

INT_MAX = 2 ** 31 - 1                 # 2,147,483,647; the smallest int is -2,147,483,648


def reverse(x):                       # 0 when the reverse doesn't fit in 32 bits
    sign = -1 if x < 0 else 1
    x = abs(x)                        # Python's % would make the digits of a negative number positive
    last = 7 if sign == 1 else 8      # the largest last digit that still fits
    result = 0
    while x != 0:
        digit = x % 10
        x //= 10
        if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > last):
            return 0                  # checked before result * 10 could pass the limit
        result = result * 10 + digit
    return sign * result


for x in (123, -123, 120, 1534236469, 1463847412, -2147483648):
    print(x, "->", reverse(x))

# 123 -> 321
# -123 -> -321
# 120 -> 21
# 1534236469 -> 0
# 1463847412 -> 2147483641
# -2147483648 -> 0

public class Main {
    static int reverse(int x) {        // 0 when the reverse doesn't fit in 32 bits
        int result = 0;
        while (x != 0) {
            int digit = x % 10;        // negative when x is: Java keeps the dividend's sign
            x /= 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
            result = result * 10 + digit;   // safe: checked before it could pass the limit
        }
        return result;
    }

    public static void main(String[] args) {
        for (int x : new int[]{123, -123, 120, 1534236469, 1463847412, Integer.MIN_VALUE})
            System.out.println(x + " -> " + reverse(x));
    }
}

// 123 -> 321
// -123 -> -321
// 120 -> 21
// 1534236469 -> 0
// 1463847412 -> 2147483641
// -2147483648 -> 0

const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);

function reverse(x) {                  // 0 when the reverse doesn't fit in 32 bits
    let result = 0;
    while (x !== 0) {
        const digit = x % 10;          // negative when x is, as in C++ and Java
        x = Math.trunc(x / 10);
        if (result > Math.trunc(INT_MAX / 10) || (result === Math.trunc(INT_MAX / 10) && digit > 7)) return 0;
        if (result < Math.trunc(INT_MIN / 10) || (result === Math.trunc(INT_MIN / 10) && digit < -8)) return 0;
        result = result * 10 + digit;  // checked before it could pass the limit
    }
    return result;
}

for (const x of [123, -123, 120, 1534236469, 1463847412, INT_MIN])
    console.log(x, "->", reverse(x));

// 123 -> 321
// -123 -> -321
// 120 -> 21
// 1534236469 -> 0
// 1463847412 -> 2147483641
// -2147483648 -> 0

1,534,236,469 now gives 0, 120 gives 21 (the trailing 0 becomes a leading 0 and disappears), and 1,463,847,412 gives 2,147,483,641, which fits. −2,147,483,648 gives 0: its reverse, −8,463,847,412, is far past the smallest int.

In C++, Java and JavaScript the digit of a negative number is negative, so one loop handles both signs with the 7 and the −8. Python's % makes those digits positive, so its version takes the sign off first and lets the last digit be at most 7 or 8. JavaScript could hold the true reverse (its numbers are exact up to 2⁵³) and check at the end instead, but the version above keeps the check the problem means.

Other bases

Nothing in the loop is special to 10. In base b, n % b is the last digit and n / b drops it; reading digits back multiplies by b and adds, left to right (Horner's rule):

#include <bits/stdc++.h>
using namespace std;

const string DIGITS = "0123456789ABCDEF";

string toBase(long long n, int base) { // n >= 0 written in base 2 to 16
    string out;
    do {
        out = DIGITS[n % base] + out;  // the last digit goes in front
        n /= base;
    } while (n != 0);
    return out;
}

long long fromBase(const string& s, int base) {   // Horner's rule: one place left, then add the digit
    long long value = 0;
    for (char ch : s) value = value * base + (long long) DIGITS.find(ch);
    return value;
}

int main() {
    for (pair<long long, int> c : vector<pair<long long, int>>{{13, 2}, {255, 16}, {4837, 8}}) {
        string s = toBase(c.first, c.second);
        printf("%lld in base %d is %s, and back: %lld\n", c.first, c.second, s.c_str(), fromBase(s, c.second));
    }
}

// 13 in base 2 is 1101, and back: 13
// 255 in base 16 is FF, and back: 255
// 4837 in base 8 is 11345, and back: 4837

DIGITS = "0123456789ABCDEF"


def to_base(n, base):                 # n >= 0 written in base 2 to 16
    out = ""
    while True:
        out = DIGITS[n % base] + out  # the last digit goes in front
        n //= base
        if n == 0:
            return out


def from_base(s, base):               # Horner's rule: one place left, then add the digit
    value = 0
    for ch in s:
        value = value * base + DIGITS.index(ch)
    return value


for n, base in ((13, 2), (255, 16), (4837, 8)):
    s = to_base(n, base)
    print(f"{n} in base {base} is {s}, and back: {from_base(s, base)}")

# 13 in base 2 is 1101, and back: 13
# 255 in base 16 is FF, and back: 255
# 4837 in base 8 is 11345, and back: 4837

public class Main {
    static final String DIGITS = "0123456789ABCDEF";

    static String toBase(long n, int base) {   // n >= 0 written in base 2 to 16
        StringBuilder out = new StringBuilder();
        do {
            out.insert(0, DIGITS.charAt((int) (n % base)));   // the last digit goes in front
            n /= base;
        } while (n != 0);
        return out.toString();
    }

    static long fromBase(String s, int base) {   // Horner's rule: one place left, then add the digit
        long value = 0;
        for (char ch : s.toCharArray()) value = value * base + DIGITS.indexOf(ch);
        return value;
    }

    public static void main(String[] args) {
        long[][] cases = {{13, 2}, {255, 16}, {4837, 8}};
        for (long[] c : cases) {
            String s = toBase(c[0], (int) c[1]);
            System.out.println(c[0] + " in base " + c[1] + " is " + s + ", and back: " + fromBase(s, (int) c[1]));
        }
    }
}

// 13 in base 2 is 1101, and back: 13
// 255 in base 16 is FF, and back: 255
// 4837 in base 8 is 11345, and back: 4837

const DIGITS = "0123456789ABCDEF";

function toBase(n, base) {             // n >= 0 written in base 2 to 16
    let out = "";
    do {
        out = DIGITS[n % base] + out;  // the last digit goes in front
        n = Math.floor(n / base);
    } while (n !== 0);
    return out;
}

function fromBase(s, base) {           // Horner's rule: one place left, then add the digit
    let value = 0;
    for (const ch of s) value = value * base + DIGITS.indexOf(ch);
    return value;
}

for (const [n, base] of [[13, 2], [255, 16], [4837, 8]]) {
    const s = toBase(n, base);
    console.log(`${n} in base ${base} is ${s}, and back: ${fromBase(s, base)}`);
}

// 13 in base 2 is 1101, and back: 13
// 255 in base 16 is FF, and back: 255
// 4837 in base 8 is 11345, and back: 4837

13 is 1101 in binary: 8 + 4 + 0 + 1. A number has ⌊log_b n⌋ + 1 digits in base b, so a bigger base means fewer digits: 4,837 takes 4 in base 10, 5 in base 8 and 13 in binary.

Spreadsheet columns look like base 26 but aren't quite. They run A to Z, then AA, AB and so on, with no letter for zero: the digits go from 1 to 26 instead of 0 to 25. Plain base 26 breaks exactly where a remainder is 0. Run as plain base 26 with @ (the character before A) for the 0, it printed A@ for 26, B@ for 52 and AA@ for 702. The fix is to take 1 off before each digit:

#include <bits/stdc++.h>
using namespace std;

string columnTitle(int n) {            // 1 -> A, 26 -> Z, 27 -> AA: base 26 with digits 1 to 26, no zero
    string title;
    while (n > 0) {
        n--;                           // shift 1..26 down to 0..25 before taking the digit
        title = char('A' + n % 26) + title;
        n /= 26;
    }
    return title;
}

int main() {
    for (int n : {1, 26, 27, 52, 701, 702, 703})
        printf("%d %s\n", n, columnTitle(n).c_str());
}

// 1 A
// 26 Z
// 27 AA
// 52 AZ
// 701 ZY
// 702 ZZ
// 703 AAA

def column_title(n):                  # 1 -> A, 26 -> Z, 27 -> AA: base 26 with digits 1 to 26, no zero
    title = ""
    while n > 0:
        n -= 1                        # shift 1..26 down to 0..25 before taking the digit
        title = chr(ord("A") + n % 26) + title
        n //= 26
    return title


for n in (1, 26, 27, 52, 701, 702, 703):
    print(n, column_title(n))

# 1 A
# 26 Z
# 27 AA
# 52 AZ
# 701 ZY
# 702 ZZ
# 703 AAA

public class Main {
    static String columnTitle(int n) {   // 1 -> A, 26 -> Z, 27 -> AA: base 26 with digits 1 to 26, no zero
        StringBuilder title = new StringBuilder();
        while (n > 0) {
            n--;                         // shift 1..26 down to 0..25 before taking the digit
            title.insert(0, (char) ('A' + n % 26));
            n /= 26;
        }
        return title.toString();
    }

    public static void main(String[] args) {
        for (int n : new int[]{1, 26, 27, 52, 701, 702, 703})
            System.out.println(n + " " + columnTitle(n));
    }
}

// 1 A
// 26 Z
// 27 AA
// 52 AZ
// 701 ZY
// 702 ZZ
// 703 AAA

function columnTitle(n) {              // 1 -> A, 26 -> Z, 27 -> AA: base 26 with digits 1 to 26, no zero
    let title = "";
    while (n > 0) {
        n--;                           // shift 1..26 down to 0..25 before taking the digit
        title = String.fromCharCode(65 + n % 26) + title;
        n = Math.floor(n / 26);
    }
    return title;
}

for (const n of [1, 26, 27, 52, 701, 702, 703])
    console.log(n, columnTitle(n));

// 1 A
// 26 Z
// 27 AA
// 52 AZ
// 701 ZY
// 702 ZZ
// 703 AAA

Two dashed bands for column 52. Red, plain base 26: 52 = 2 × 26 + 0, an arrow to the digit tiles 2 and 0, an arrow marked letters to the tiles B and a red @, and a cross with the words no letter for 0. Green, take 1 off first: step 1, 52 − 1 = 51 = 1 × 26 + 25, an arrow to a Z tile; step 2, 1 − 1 = 0 = 0 × 26 + 0, an arrow to an A tile; beside them, each letter goes in front: the tiles A and Z with a tick, and column 52 is AZ. Focal line: subtract 1 before each digit: the digits run 1 to 26. Title: no zero digit in column titles.

26 − 1 = 25 is Z with nothing left over. 52 − 1 = 51 is 1 × 26 + 25: Z, then 1 − 1 = 0 is A, so AZ. 702 is ZZ and 703 is AAA.

Numbers longer than any integer

When a number has 200 digits it comes as a string, and the arithmetic is the paper method, digit by digit. Multiply Strings asks for the product of two digit strings without converting them.

Count the digits from the left from 0. Digit i of an m-digit num1 is worth 10 to the power m − 1 − i, and digit j of an n-digit num2 is worth 10 to the n − 1 − j, so their product lands m + n − 2 − i − j places from the right. In a result of m + n cells, that's cell i + j + 1, and whatever passes 9 carries into cell i + j. A product of an m-digit and an n-digit number never has more than m + n digits, so m + n cells are always enough:

Two dashed panels for 123 × 45. Left, digit × digit, and its cell: the digits of 45 across the top as blue tiles, j = 0 and 1, and the digits of 123 down the side as orange tiles, i = 0, 1 and 2; each of the six boxes reads its product and its cell, 1 × 4 = 4 in cell 1, 1 × 5 = 5 and 2 × 4 = 8 in cell 2, 2 × 5 = 10 and 3 × 4 = 12 in cell 3, 3 × 5 = 15 in cell 4, coloured by cell, with the line same colour: same i + j, same cell. Right, the cells: 123 × 45 over five tiles numbered 0 to 4, coloured the same way and holding 0, 5, 5, 3 and 5, the first one pale, and after every pair and carry: 0 5 5 3 5 = 5535. Focal line: digit i × digit j lands in cell i + j + 1. Title: each digit pair has a place.

#include <bits/stdc++.h>
using namespace std;

string multiply(const string& num1, const string& num2) {   // two numbers as digit strings
    int m = num1.size(), n = num2.size();
    vector<int> cells(m + n, 0);       // the product has at most m + n digits
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--) {
            int product = (num1[i] - '0') * (num2[j] - '0');
            int total = product + cells[i + j + 1];   // digit i times digit j lands at i + j + 1
            cells[i + j + 1] = total % 10;
            cells[i + j] += total / 10;               // the carry moves one place left
        }
    string text;
    for (int c : cells)
        if (!(text.empty() && c == 0)) text += char('0' + c);   // skip the leading zeros
    return text.empty() ? "0" : text;  // every cell 0: the product is 0
}

int main() {
    printf("%s %s %s\n", multiply("123", "456").c_str(), multiply("0", "52").c_str(),
           multiply("999", "999").c_str());
}

// 56088 0 998001

def multiply(num1, num2):             # two numbers as digit strings
    m, n = len(num1), len(num2)
    cells = [0] * (m + n)             # the product has at most m + n digits
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            product = (ord(num1[i]) - ord("0")) * (ord(num2[j]) - ord("0"))
            total = product + cells[i + j + 1]   # digit i times digit j lands at i + j + 1
            cells[i + j + 1] = total % 10
            cells[i + j] += total // 10          # the carry moves one place left
    text = "".join(map(str, cells)).lstrip("0")  # skip the leading zeros
    return text or "0"                # every cell 0: the product is 0


print(multiply("123", "456"), multiply("0", "52"), multiply("999", "999"))

# 56088 0 998001

public class Main {
    static String multiply(String num1, String num2) {   // two numbers as digit strings
        int m = num1.length(), n = num2.length();
        int[] cells = new int[m + n];      // the product has at most m + n digits
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int total = product + cells[i + j + 1];   // digit i times digit j lands at i + j + 1
                cells[i + j + 1] = total % 10;
                cells[i + j] += total / 10;               // the carry moves one place left
            }
        StringBuilder text = new StringBuilder();
        for (int c : cells)
            if (!(text.length() == 0 && c == 0)) text.append(c);   // skip the leading zeros
        return text.length() == 0 ? "0" : text.toString();     // every cell 0: the product is 0
    }

    public static void main(String[] args) {
        System.out.println(multiply("123", "456") + " " + multiply("0", "52") + " "
            + multiply("999", "999"));
    }
}

// 56088 0 998001

function multiply(num1, num2) {        // two numbers as digit strings
    const m = num1.length, n = num2.length;
    const cells = new Array(m + n).fill(0);   // the product has at most m + n digits
    for (let i = m - 1; i >= 0; i--)
        for (let j = n - 1; j >= 0; j--) {
            const product = (num1.charCodeAt(i) - 48) * (num2.charCodeAt(j) - 48);
            const total = product + cells[i + j + 1];   // digit i times digit j lands at i + j + 1
            cells[i + j + 1] = total % 10;
            cells[i + j] += Math.floor(total / 10);     // the carry moves one place left
        }
    const text = cells.join("").replace(/^0+/, "");   // skip the leading zeros
    return text || "0";                // every cell 0: the product is 0
}

console.log(multiply("123", "456"), multiply("0", "52"), multiply("999", "999"));

// 56088 0 998001

123 × 456 came out 56,088 in all four languages, 999 × 999 = 998,001, and two 200-digit numbers multiplied this way matched Python's own integers digit for digit. Every pair of digits is multiplied once: O(m · n) time and O(m + n) cells.

The leading zeros matter twice: 123 × 456 fills only 5 of its 6 cells, and 0 × 52 fills none of its 3, which must come out as 0, not as an empty string or 000.

Carry the One. Multiply two numbers the way the code does. For each pair of digits, pick the cell its product lands in and watch the carry move left; at the end, decide which leading zeros go.

Carry the One: place each digit product, then strip the leading zeros

Spotting it

The clues: "the digits of n", "reverse", "without converting it to a string", "may not fit in a 32-bit integer", numbers given as strings, a column title or a base. Near misses:

Roman to Integer reads symbols, not place values: one lookup per symbol and one comparison with the next (Strings, Parsing in One Pass).
String to Integer (atoi) builds a number from characters with the same overflow check before the multiply, but most of its work is signs, spaces and stray characters (Strings, Parsing in One Pass).
Happy Number repeats "add up the squares of the digits", but the question is whether that sequence loops, which is cycle detection (Linked List, Fast and Slow Pointers).

Mistakes that cost an interview

Checking for overflow after it happened. The first loop above printed 1,056,389,759 in C++ and Java for 1,534,236,469. Compare against 214,748,364 before the multiply.

while n > 0 for the digits of 0. It counts 0 digits. Divide first, test after.

Python's % on a negative number. −123 % 10 is 7 in Python and −3 in C++, Java and JavaScript. Take the sign off first, or know which one your language does.

Counting digits with logarithms. ⌊log₁₀ n⌋ + 1 said 16 for 999,999,999,999,999 and log(n) / log(10) said 3 for 1,000, in all four languages. Count with the loop.

Plus One by turning the digits into a number. On these 19 digits:

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> digits = {9, 2, 2, 3, 3, 7, 2, 0, 3, 6, 8, 5, 4, 7, 7, 5, 8, 0, 7};
    long long number = 0;
    for (int d : digits) number = number * 10 + d;   // the largest long long, exactly
    printf("%lld\n", number + 1);                    // plus one: past the largest long long
}

// -9223372036854775808

digits = [9, 2, 2, 3, 3, 7, 2, 0, 3, 6, 8, 5, 4, 7, 7, 5, 8, 0, 7]
number = int("".join(map(str, digits)))   # right only because Python's ints have no size limit
print(number + 1)

# 9223372036854775808

public class Main {
    public static void main(String[] args) {
        int[] digits = {9, 2, 2, 3, 3, 7, 2, 0, 3, 6, 8, 5, 4, 7, 7, 5, 8, 0, 7};
        long number = 0;
        for (int d : digits) number = number * 10 + d;   // Long.MAX_VALUE, exactly
        System.out.println(number + 1);                  // plus one: it wraps around
    }
}

// -9223372036854775808

const digits = [9, 2, 2, 3, 3, 7, 2, 0, 3, 6, 8, 5, 4, 7, 7, 5, 8, 0, 7];
const number = Number(digits.join(""));   // a double: about 16 significant digits
console.log(number + 1);

// 9223372036854776000

C++ and Java printed −9,223,372,036,854,775,808: 9,223,372,036,854,775,807 is the largest 64-bit integer, and one more wraps it to the smallest (in C++, undefined behaviour again). JavaScript printed 9,223,372,036,854,776,000: a double keeps about 16 significant digits. Python was right only because its ints have no size limit, and the array can be 100 digits long. Carry through the array instead.

Spreadsheet columns as plain base 26. 26 came out A@. Take 1 off before each digit.

Leaving the leading zeros in Multiply Strings. Without the strip, 0 × 52 returned '000'; with a strip and nothing to fall back on, it returned '', an empty string. Strip, and return "0" when nothing is left.

Check yourself

Quiz

1 / 6

Multiple choice

This counts the digits of n. What does it give for n = 0?

int count = 0;
while (n > 0) {
    n /= 10;
    count++;
}

Practice

In this section, easy to hard:

Count Digits of a Number: the digit loop, and 0 has one digit.
Palindrome Number: reverse the back half and compare.
Armstrong Number: the loop twice, digits then powers.
Plus One: a carry through an array.
Excel Sheet Column Title: base 26 with no zero digit.
Reverse Integer: the overflow check before the multiply.
Multiply Strings: digit products at i + j + 1, then the leading zeros.

Next: Divisors, GCD and Primes, where the loop runs over a number's divisors instead of its digits.