Working with digits

On paper, 121 is a row of three digits. To your code, it is one value. You cannot index into it like an array.

This lesson gives you one small loop that takes a number apart, digit by digit. Count digits, reverse a number, check a palindrome: all of them use that same loop.

The one move: peel the last digit

Two operations do all the work:

• n % 10 gives the last digit. The remainder after dividing by 10 is always the units digit.
• n / 10, with the decimals thrown away, drops the last digit. Each language writes that differently:

Repeat both until nothing is left:

┌──────────────────────────────────────────────┐
│                                              │
│     n      last digit     what is left       │
│            n % 10         floor(n / 10)      │
│   7789        9               778            │
│    778        8                77            │
│     77        7                 7            │
│      7        7                 0   ← stop   │
│                                              │
└──────────────────────────────────────────────┘

The digits come out in reverse order: 9, 8, 7, 7. Keep that in mind. It is the reason reversing a number is easy.

JavaPythonTypeScript

void printDigits(int n) {
    while (n > 0) {
        int digit = n % 10; // the last digit
        System.out.println(digit);
        n = n / 10; // drop it
    }
}

The loop runs only while n > 0, so handle the sign first. The languages disagree on negative numbers:

• -7 % 10 is -7 in Java and TypeScript, but 3 in Python.
• -7 / 10 is 0 in Java. -7 // 10 is -1 in Python, and Math.floor(-7 / 10) is -1 in TypeScript.

Make the number positive, peel it, then put the sign back.

What it costs

Each pass removes one digit. So the loop runs once per digit.

A number n has about log₁₀ n digits, so the loop is O(log n). It is the halving loop from Time and space complexity, cutting by 10 each time instead of 2.

Read the problem

Ask these before you code:

• Negative numbers? The minus sign sits only at the front. So every negative number is false.
• Ends in 0? 10 read backwards is "01". Only 0 itself is a palindrome that ends in 0.
• One digit? Always true.
• How big? At most 10 digits. Speed is not the problem here. The follow-up is: solve it without a string.

The input is one number, not an array. So the cost depends on its digit count, not on a length n.

Brute force: turn it into a string

The first idea: make a string, reverse it, compare.

┌──────────────────────────────────────────────────┐
│                                                  │
│   1221 ──to text──▶ "1221" ──reverse──▶ "1221"   │
│                        │                   │     │
│                        └───── equal? ──────┘     │
│                                true              │
│                                                  │
└──────────────────────────────────────────────────┘

JavaPythonTypeScript

boolean isPalindrome(int x) {
    String s = String.valueOf(x);
    return s.equals(new StringBuilder(s).reverse().toString());
}

• The text of -121 is "-121", and its reverse is "121-". So negatives return false with no extra check.
• Time: one pass to build the string, one to reverse it, one to compare. O(d) for d digits.
• Space: two strings of d characters, so O(d).

It is correct and fast. But the follow-up says no strings, and the interviewer wants to see you work with the number itself.

The key insight

You can build the reverse with arithmetic. The peel loop already hands you the digits from right to left. Each new digit goes on the end of rev:

┌───────────────────────────────────────────────────┐
│                                                   │
│   rev = 12      rev × 10 = 120     + 2 = 122      │
│   ┌───┬───┐     ┌───┬───┬───┐     ┌───┬───┬───┐   │
│   │ 1 │ 2 │ ──▶ │ 1 │ 2 │ 0 │ ──▶ │ 1 │ 2 │ 2 │   │
│   └───┴───┘     └───┴───┴───┘     └───┴───┴───┘   │
│                                                   │
└───────────────────────────────────────────────────┘

So one line does it: rev = rev * 10 + digit.

One trap: the loop eats x until it is 0. Save a copy first, so you have something to compare with at the end.

Optimal: reverse with maths

1. Return false for a negative number.
2. Save original = x. Start rev at 0.
3. While x > 0: peel the last digit, push it onto rev, drop it from x.
4. Return whether rev equals original.

Here it is on 1221. The pointer marks the digit each pass reads.

JavaPythonTypeScript

boolean isPalindrome(int x) {
    if (x < 0) return false;
    int original = x;
    long rev = 0; // long: a reversed int can pass the int limit
    while (x > 0) {
        int digit = x % 10;
        rev = rev * 10 + digit; // push the digit onto the end of rev
        x = x / 10; // drop it from x
    }
    return rev == original;
}

• Time: one pass per digit, so O(d), which is O(log x).
• Space: two numbers, so O(1).
• 0: the loop never runs, rev stays 0, and 0 equals 0. True.
• 10: rev ends as 1, which is not 10. False, with no special case.
• Big values: 2,147,483,647 reversed is 7,463,847,412. That is past the largest Java int, so the Java version keeps rev in a long. A Python int has no limit, and a TypeScript number holds it exactly.

Side by side

Here d is the digit count, at most 10.

How to spot this pattern

The template. Only the middle line changes from problem to problem:

JavaPythonTypeScript

while (n > 0) {
    int digit = n % 10;
    // use digit: count it, add it, compare it
    n = n / 10;
}

The other problems on this lesson's list:

An Armstrong number uses the loop twice: once to count the k digits, once to add each digit to the power k. 153 is 1 + 125 + 27, so it is one.

Factorial is the odd one out. It is a plain loop that multiplies 1 × 2 × … × n, so O(n).

Watch the size. Factorials grow fast:

• Java: 12! is the largest that fits an int, and 20! the largest that fits a long.
• Python: an int has no limit, so any factorial is exact.
• TypeScript: 18! is the largest below Number.MAX_SAFE_INTEGER. Past that, use BigInt.

take U forwardYouTube

Read more

• Remainder (%) on MDN, including what it does with negative numbers
• Binary arithmetic operations in the Python reference, for // and % on negative numbers
• Narcissistic number on Wikipedia, the maths name for Armstrong numbers
• Palindrome Number on takeUforward, to solve it yourself

Next: divisors, primes and GCD, where one loop stops at the square root.