3918. Sum of Primes Between Number and Its Reverse

MediumMathNumber Theory

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

Your task involves a number formed by reversing the digits of n. Let's call this reversed number r. For example, if n = 123, then r = 321. If n = 100, then r would be 1 (since reversing 100 gives 001, which equals 1).

Once you have both n and r, you need to look at the range of integers between them. Specifically, the range goes from min(n, r) to max(n, r), and both endpoints are inclusive. Using min and max ensures the range is valid regardless of whether n or r is larger.

Within this range, you must find all the prime numbers. A prime number is a number greater than 1 that has no positive divisors other than 1 and itself (for example, 2, 3, 5, 7, 11, and so on).

Finally, return the sum of all the prime numbers found in that range [min(n, r), max(n, r)].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Number Theory?

This problem maps to Number Theory through a short path in the full flowchart.

The problem involves prime numbers or number-theoretic properties.

Open in Flowchart

Intuition

The core of this problem is summing up prime numbers within a certain range, so naturally we need an efficient way to check whether a number is prime.

The first observation is about the size of the numbers involved. When we reverse the digits of n, the reversed number r has the same number of digits as n (or fewer, if there are trailing zeros). This means both n and r, along with every number in the range [min(n, r), max(n, r)], stay within a small, bounded limit. Based on the constraints, this limit does not exceed 1000.

Since all the numbers we care about fall under 1000, instead of checking primality one number at a time using trial division, we can precompute the primality of every number from 0 to 1000 in advance. The classic tool for this is the Sieve of Eratosthenes, which efficiently marks all non-prime numbers by starting from each prime and crossing out its multiples. After running the sieve once, we have a lookup table is_prime where is_prime[x] instantly tells us whether x is prime.

With this precomputed table ready, the actual solution becomes straightforward. We:

Compute r by reversing the string form of n and converting it back to an integer.
Determine the range boundaries using low = min(n, r) and high = max(n, r).
Iterate through every integer from low to high, and whenever is_prime[x] is True, add that number to our running sum.

Because the sieve is built only once (and shared across all calls), each query simply scans a small range and adds up the primes, making the whole process fast and clean.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Precompute Primes

We note that the reversed number r of n will not exceed 1000, so we can precompute all prime numbers up to 1000 using the Sieve of Eratosthenes.

Step 1: Build the sieve.

We create a boolean array is_prime of size limit + 1 (where limit = 1000), initially marking every entry as True. Since 0 and 1 are not prime, we set is_prime[0] = is_prime[1] = False.

Then we iterate i from 2 up to int(limit**0.5). Whenever is_prime[i] is still True, i is a prime, so we mark all of its multiples as non-prime. We start crossing out from i * i (because any smaller multiple of i would already have been marked by a smaller prime factor) and step forward by i each time:

for i in range(2, int(limit**0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, limit + 1, i):
            is_prime[j] = False

This array is built once at module load time, so it is reused across every call without recomputation.

Step 2: Compute the reversed number.

Inside the method, we reverse the digits of n by converting it to a string, reversing the string with slicing [::-1], and converting it back to an integer:

r = int(str(n)[::-1])

Converting to int automatically discards any leading zeros that appear after reversal (for example, 100 reversed becomes "001", which turns into 1).

Step 3: Determine the range and sum the primes.

We compute low = min(n, r) and high = max(n, r), then iterate through every integer in the range [low, high]. For each integer x, we check is_prime[x] directly in O(1) time, and add it to the answer if it is prime:

low = min(n, r)
high = max(n, r)
return sum(x for x in range(low, high + 1) if is_prime[x])

The generator expression neatly combines the iteration, the primality filter, and the summation into a single line.

Complexity Analysis:

The sieve takes O(M log log M) time, where M = 1000, but this runs only once.
Each query iterates over the range, which is at most O(M), with O(1) prime lookups.
The space used by the is_prime array is O(M).

Example Walkthrough

Let's trace through the solution approach with a small example: n = 13.

Setup: The sieve is already built.

Before any query runs, the Sieve of Eratosthenes has precomputed is_prime[0..1000]. For the numbers we'll care about, the relevant lookups are:

x	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
is_prime	T	F	T	F	F	F	T	F	T	F	F	F	T	F	F	F	F	F	T	F	T

Step 1: Compute the reversed number r.

We reverse the digits of n = 13:

Convert to string: "13"
Reverse with slicing: "31"
Convert back to int: r = 31

There are no trailing zeros here, so nothing gets discarded.

Step 2: Determine the range boundaries.

We compute the inclusive bounds:

low = min(13, 31) = 13
high = max(13, 31) = 31

So our range is [13, 31].

Step 3: Scan the range and sum the primes.

We iterate x from 13 to 31, consulting is_prime[x] in O(1) for each:

x	is_prime[x]?	Action	Running Sum
13	✅ True	add 13	13
14	❌ False	skip	13
15	❌ False	skip	13
16	❌ False	skip	13
17	✅ True	add 17	30
18	❌ False	skip	30
19	✅ True	add 19	49
20	❌ False	skip	49
21	❌ False	skip	49
22	❌ False	skip	49
23	✅ True	add 23	72
24–28	❌ False	skip	72
29	✅ True	add 29	101
30	❌ False	skip	101
31	✅ True	add 31	132

Result.

The primes found in [13, 31] are 13, 17, 19, 23, 29, 31, and their sum is:

13 + 17 + 19 + 23 + 29 + 31 = 132

So the function returns 132.

This walkthrough highlights the elegance of the approach: the expensive primality work was done once by the sieve, leaving each query to simply reverse the number, set the bounds, and add up the precomputed primes in a single linear scan.

Solution Implementation

1from typing import List
2
3# Precompute prime numbers up to a fixed limit using the Sieve of Eratosthenes.
4LIMIT = 1000
5
6# is_prime[i] indicates whether i is a prime number.
7is_prime: List[bool] = [True] * (LIMIT + 1)
8is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime numbers.
9
10# Mark all non-prime numbers up to sqrt(LIMIT).
11for i in range(2, int(LIMIT ** 0.5) + 1):
12    if is_prime[i]:
13        # Mark all multiples of i starting from i*i as non-prime.
14        for multiple in range(i * i, LIMIT + 1, i):
15            is_prime[multiple] = False
16
17
18class Solution:
19    def sumOfPrimesInRange(self, n: int) -> int:
20        # Reverse the digits of n to obtain the other boundary of the range.
21        reversed_n = int(str(n)[::-1])
22
23        # Determine the inclusive lower and upper bounds of the range.
24        low = min(n, reversed_n)
25        high = max(n, reversed_n)
26
27        # Sum up all prime numbers within the inclusive range [low, high].
28        return sum(value for value in range(low, high + 1) if is_prime[value])
29

1class Solution {
2    // Upper bound for the sieve of Eratosthenes.
3    private static final int LIMIT = 1000;
4
5    // isPrime[i] is true if and only if i is a prime number.
6    private static final boolean[] isPrime = new boolean[LIMIT + 1];
7
8    // Static initializer block: builds the prime table once when the class is loaded.
9    static {
10        // Initially assume every number is prime.
11        for (int i = 0; i <= LIMIT; i++) {
12            isPrime[i] = true;
13        }
14
15        // 0 and 1 are not prime by definition.
16        isPrime[0] = false;
17        isPrime[1] = false;
18
19        // Standard sieve of Eratosthenes.
20        for (int i = 2; i * i <= LIMIT; i++) {
21            if (isPrime[i]) {
22                // Mark all multiples of i (starting from i*i) as non-prime.
23                for (int j = i * i; j <= LIMIT; j += i) {
24                    isPrime[j] = false;
25                }
26            }
27        }
28    }
29
30    /**
31     * Computes the sum of all prime numbers in the inclusive range
32     * bounded by n and its digit-reversed value.
33     *
34     * @param n the input number
35     * @return the sum of primes within the range [min(n, reversed), max(n, reversed)]
36     */
37    public int sumOfPrimesInRange(int n) {
38        // Reverse the digits of n to obtain the other boundary.
39        int reversed = Integer.parseInt(
40                new StringBuilder(String.valueOf(n)).reverse().toString());
41
42        // Determine the lower and upper bounds of the range.
43        int low = Math.min(n, reversed);
44        int high = Math.max(n, reversed);
45
46        // Accumulate the sum of every prime in the range.
47        int sum = 0;
48        for (int x = low; x <= high; x++) {
49            if (isPrime[x]) {
50                sum += x;
51            }
52        }
53
54        return sum;
55    }
56}
57

1// Upper bound for the sieve of Eratosthenes
2const int kMaxValue = 1000;
3
4// is_prime[i] indicates whether i is a prime number
5bool is_prime[kMaxValue + 1];
6
7// Precompute the prime table once using a lambda invoked at static init time
8auto init = [] {
9    // Initially assume every number is prime
10    for (int i = 0; i <= kMaxValue; ++i) {
11        is_prime[i] = true;
12    }
13    // 0 and 1 are not prime by definition
14    is_prime[0] = is_prime[1] = false;
15
16    // Standard sieve of Eratosthenes
17    for (int i = 2; i * i <= kMaxValue; ++i) {
18        if (is_prime[i]) {
19            // Mark all multiples of i (starting from i*i) as non-prime
20            for (int j = i * i; j <= kMaxValue; j += i) {
21                is_prime[j] = false;
22            }
23        }
24    }
25    return 0;
26}();
27
28class Solution {
29public:
30    int sumOfPrimesInRange(int n) {
31        // Build the reversed number of n digit by digit
32        int reversed = 0;
33        int temp = n;
34        while (temp) {
35            reversed = reversed * 10 + temp % 10;  // Append the last digit
36            temp /= 10;                            // Drop the last digit
37        }
38
39        // The range is defined by n and its reversed value
40        int low = min(n, reversed);
41        int high = max(n, reversed);
42
43        // Sum up all prime numbers within [low, high]
44        int ans = 0;
45        for (int x = low; x <= high; ++x) {
46            if (is_prime[x]) {
47                ans += x;
48            }
49        }
50        return ans;
51    }
52};
53

1// Upper bound for the prime sieve.
2const LIMIT = 1000;
3
4// Sieve of Eratosthenes: isPrime[i] is true when i is a prime number.
5const isPrime: boolean[] = new Array(LIMIT + 1).fill(true);
6
7// 0 and 1 are not prime numbers.
8isPrime[0] = false;
9isPrime[1] = false;
10
11// Mark all composite numbers up to LIMIT as not prime.
12for (let i = 2; i * i <= LIMIT; i++) {
13    // Only start from a prime base; multiples of composites are already marked.
14    if (isPrime[i]) {
15        // Begin at i * i because smaller multiples were marked by smaller primes.
16        for (let j = i * i; j <= LIMIT; j += i) {
17            isPrime[j] = false;
18        }
19    }
20}
21
22/**
23 * Computes the sum of all prime numbers within the inclusive range
24 * bounded by a number and its digit-reversed counterpart.
25 *
26 * @param n - The input number whose reversal defines the other range bound.
27 * @returns The sum of every prime in the range [min(n, reversed), max(n, reversed)].
28 */
29function sumOfPrimesInRange(n: number): number {
30    // Reverse the decimal digits of n to obtain the second range bound.
31    const reversed = parseInt(n.toString().split('').reverse().join(''));
32
33    // Determine the inclusive lower and upper bounds of the range.
34    const low = Math.min(n, reversed);
35    const high = Math.max(n, reversed);
36
37    // Accumulate the sum of every prime number within the range.
38    let sum = 0;
39    for (let x = low; x <= high; x++) {
40        if (isPrime[x]) {
41            sum += x;
42        }
43    }
44
45    return sum;
46}
47

Time and Space Complexity

Time Complexity: O(n)

The sieve precomputation runs once at module load time and is bounded by the fixed constant limit = 1000, costing O(M log log M), which is constant with respect to the input n and therefore not counted per call. Within sumOfPrimesInRange, computing the reversed number r from n takes time proportional to the number of digits, i.e., O(log n). The dominant work is the sum over range(low, high + 1), where low = min(n, r) and high = max(n, r). In the worst case the span between n and its reversal is on the order of n, so iterating over this range and checking is_prime[x] (an O(1) lookup) costs O(n). Hence the overall time complexity is O(n).
Space Complexity: O(M)

The precomputed boolean array is_prime has length limit + 1, requiring O(M) space where M = 1000. The function itself only uses a constant number of auxiliary variables (r, low, high) and the generator expression in sum does not materialize a list, so it adds only O(1) extra space. Therefore the total space complexity is O(M).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Hardcoding the sieve `LIMIT` too small

The most dangerous assumption in this solution is that the reversed number r "will not exceed 1000." This is only true if the input n itself is constrained to be at most 1000 (or a similarly small bound). If the problem allows larger inputs — say n up to 10^4, 10^5, or beyond — then both n and its reverse r can exceed 1000, and the line:

is_prime[value]  # value can now be > LIMIT

will throw an IndexError: list index out of range, because the is_prime array only has indices 0 through 1000.

Why it happens: The sieve size is fixed at module load time, but the actual range [min(n, r), max(n, r)] depends entirely on the input magnitude, which the precomputation does not account for.

Solution: Derive the limit from the true maximum possible value of n and r, not a guessed constant. Reversing a number never increases its digit count, so the maximum value in any query is bounded by the largest possible n. Set the sieve limit accordingly based on the problem constraints:

from typing import List

# Set LIMIT to the maximum value n can take per the constraints.
# For example, if n <= 10^4, both n and its reverse are at most 10^4.
LIMIT = 10 ** 4

is_prime: List[bool] = [True] * (LIMIT + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(LIMIT ** 0.5) + 1):
    if is_prime[i]:
        for multiple in range(i * i, LIMIT + 1, i):
            is_prime[multiple] = False

If the constraint is unknown or very large, prefer a per-query primality check (trial division up to √x) so the solution never depends on a fixed array size:

class Solution:
    def sumOfPrimesInRange(self, n: int) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            if x < 4:
                return True
            if x % 2 == 0:
                return False
            i = 3
            while i * i <= x:
                if x % i == 0:
                    return False
                i += 2
            return True

        r = int(str(n)[::-1])
        low, high = min(n, r), max(n, r)
        return sum(x for x in range(low, high + 1) if is_prime(x))

Pitfall 2: Forgetting that `n` and `r` can be equal (palindromes)

When n is a palindrome (e.g., n = 121) or reduces to a single digit, n == r, so low == high and the range collapses to a single value. This is handled correctly by range(low, high + 1) (which still yields exactly one element), but a buggy variant that writes range(low, high) — dropping the + 1 — would silently exclude the endpoint and return 0 for every palindrome. Always double-check that both endpoints are inclusive, since the problem explicitly requires it.

Pitfall 3: Manual digit reversal mishandling trailing zeros

A common temptation is to reverse the number arithmetically rather than via string slicing:

r = 0
while n > 0:
    r = r * 10 + n % 10
    n //= 10

While this is correct for trailing zeros (e.g., 100 → 1), the pitfall here is mutating n in the loop. After the loop, n has become 0, so the subsequent min(n, r) / max(n, r) computation uses the wrong value. Always reverse into a separate variable using a copy of n, or use the string approach int(str(n)[::-1]), which leaves n untouched and discards leading zeros automatically through the int conversion.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know