The coding question
You're given a number as a string, and it can be very long. Return the smallest palindrome that's greater than it.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| Can it have leading zeros? | No, it's a normal positive number. |
| How long can it be? | Thousands of digits, so we can't just add one and check over and over. |
| Strictly greater, even if it's already a palindrome? | Yes. 808 should give 818. |
| Should the answer be a string? | Yes. |
A couple of examples
| Input | Output |
|---|---|
| "12345" | "12421" |
| "1991" | "2002" |
| "999" | "1001" |
Start with brute force
Add one and check if it's a palindrome. Repeat until it is.
Cost: palindromes can be far apart. For an n-digit number you might check around 10^(n/2) numbers, each costing O(n). That's hopeless for long inputs.
A better way
A palindrome is decided by its left half. The right half is just a mirror. So the smallest palindrome with the same left half is the left half copied onto the right.
If that mirrored number is already bigger than the input, it's the answer, since changing the left half at all would make it bigger. If it isn't, add one to the left half (including the middle digit for odd lengths) and mirror again. The one special case is all 9s, like 999, where the answer has an extra digit: 1001.
- If the number is all 9s, return 1, then n-1 zeros, then 1.
- Take the left half, including the middle digit if the length is odd.
- Mirror it to make a palindrome the same length. If it's bigger than the input, return it.
- Otherwise add one to the left half and mirror that. It can't get longer, since all 9s is already handled.
The code
def next_palindrome(num):
n = len(num)
if num == "9" * n:
return "1" + "0" * (n - 1) + "1"
half = num[: (n + 1) // 2]
mirrored = mirror(half, n)
if mirrored > num:
return mirrored
# Mirroring was too small, so add one to the left half and mirror again.
# The all-9s case is already handled, so this can't get longer.
bigger = str(int(half) + 1)
return mirror(bigger, n)
def mirror(half, n):
# Copy the left half onto the right. For odd lengths, skip the middle digit.
if n % 2 == 0:
return half + half[::-1]
return half + half[-2::-1]| Cost | Why | |
|---|---|---|
| Time | O(n) | A few passes over the digits |
| Space | O(n) | The new string |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- "9" gives "11", and "99" gives "101": the all-9s case.
- "1991" gives "2002": mirroring gives 1991, which isn't bigger, so 19 becomes 20.
- "808" gives "818": already a palindrome, so we have to go up.
- "1" gives "2", and "10" gives "11".
- Very long inputs: comparing strings of the same length works like comparing numbers, so we never need the whole thing as an int.
Common mistakes
- Forgetting the all-9s case. For 999, adding one to the half gives 100, the half gets longer, and the mirror comes out wrong.
- Mirroring the middle digit twice for odd lengths, turning 123 into 123321.
- Returning the input when it's already a palindrome. The question says greater.
- Comparing strings of different lengths as if they were numbers. Here they're always the same length, so it's safe, but say why.
Follow-up questions
Your code uses int(half) + 1. Is that okay for thousands of digits?
Python handles big integers, but it's slower than needed. You can add one by hand: walk from the end of the half, turning 9s into 0s until you hit a digit you can bump up. That's a clean O(n).
What about the closest palindrome, above or below?
Try a few candidates: the mirror, the mirror with the half plus one, the half minus one, plus 99...9 with one less digit and 10...01 with one more. Pick the closest that isn't the input.
What if it's the next bigger number using the same digits?
A different trick: from the right, find the first digit smaller than the one after it, swap it with the smallest bigger digit to its right, then reverse everything after it.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask questions and agree on examples |
| 5–10 | Brute force and what it costs |
| 10–15 | Explain the better idea |
| 15–30 | Write the code |
| 30–38 | Test it out loud |
| 38–45 | Follow-up questions |
Key concepts used here
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Uber.