LeetCode Problem 3918

Difficulty: 🟡 Medium
Topics: Math, Number Theory

Solution

LeetCode 3918 - Sum of Primes Between Number and Its Reverse

Problem Understanding

The problem gives us a single integer n. We first construct another integer r by reversing the digits of n.

For example:

• If n = 13, then r = 31
• If n = 10, then r = 1
• If n = 120, then r = 21

Once we have both numbers, we consider the inclusive range between them. Since either n or r could be larger, we use:

• left = min(n, r)
• right = max(n, r)

Our task is to find every prime number within that range, including both endpoints, and return their sum.

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

The constraint is very small:

• 1 <= n <= 1000

The reverse of a number up to 1000 is also small. Even the largest possible reversed value is only a few thousand. This means we do not need advanced number theory techniques such as segmented sieves or prime preprocessing over huge ranges. A straightforward primality test for each number in the range is sufficient.

Important edge cases include:

• Numbers whose reverse is smaller than the original number.
• Numbers ending with zeros, where reversing removes leading zeros.
• Ranges containing no prime numbers.
• Cases where n == r, producing a range of length one.
• Very small values such as n = 1.

Approaches

Brute Force Approach

The most direct solution is:

1. Reverse the digits of n to obtain r.
2. Compute the range [min(n, r), max(n, r)].
3. For every number in the range, determine whether it is prime.
4. If it is prime, add it to the answer.

To test whether a number x is prime, we can try every divisor from 2 up to x - 1.

This approach is correct because a number is prime exactly when no divisor in that range divides it evenly.

However, checking all possible divisors is inefficient. Each primality test costs O(x), making the overall solution slower than necessary.

Key Observation

A number greater than 1 is composite if it has a factor pair.

If x = a × b, then at least one of a or b must be less than or equal to √x.

Therefore, when checking whether a number is prime, it is sufficient to test divisors only up to √x.

This reduces the cost of each primality test from O(x) to O(√x) while preserving correctness.

Given the small constraints, this optimized primality test is more than enough.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(R²)	O(1)	Check every divisor up to the number itself
Optimal	O(R√R)	O(1)	Check divisors only up to the square root

Here R denotes the size of the largest value examined in the range.

Algorithm Walkthrough

1. Reverse the digits of n to obtain r.

This can be done by converting n to a string, reversing it, and converting it back to an integer. 2. Determine the search interval.

Compute:

• left = min(n, r)
• right = max(n, r)

This ensures we always iterate from the smaller endpoint to the larger endpoint. 3. Initialize a running sum.

Create a variable total = 0. 4. Iterate through every integer in the interval.

For each number x in [left, right], determine whether it is prime. 5. Perform primality testing.

If x < 2, it is not prime.

Otherwise, try all divisors from 2 through ⌊√x⌋.

If any divisor divides x evenly, then x is composite.

If no divisor works, then x is prime. 6. Add primes to the answer.

Whenever a number is identified as prime, add it to total. 7. Return the final sum.

After processing the entire range, return total.

Why it works

The algorithm examines every number in the required inclusive range exactly once. For each number, the primality test correctly identifies whether it is prime because every composite number must have at least one divisor not exceeding its square root. Therefore every prime in the range is added exactly once, and no composite number is added. The resulting sum is precisely the sum of all primes between n and its reverse.

Python Solution

class Solution:
    def sumOfPrimesInRange(self, n: int) -> int:
        def is_prime(num: int) -> bool:
            if num < 2:
                return False

            divisor = 2
            while divisor * divisor <= num:
                if num % divisor == 0:
                    return False
                divisor += 1

            return True

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

        left = min(n, reversed_num)
        right = max(n, reversed_num)

        total = 0

        for value in range(left, right + 1):
            if is_prime(value):
                total += value

        return total

The implementation begins with a helper function is_prime. Numbers below 2 are immediately rejected because they are not prime. For larger numbers, we test divisibility only up to the square root using the condition divisor * divisor <= num.

The reverse of the input number is computed using string reversal. We then determine the lower and upper bounds of the range with min and max.

A running total accumulates all prime values encountered while iterating through the inclusive interval. Once every number has been checked, the accumulated sum is returned.

Go Solution

func sumOfPrimesInRange(n int) int {
	isPrime := func(num int) bool {
		if num < 2 {
			return false
		}

		for divisor := 2; divisor*divisor <= num; divisor++ {
			if num%divisor == 0 {
				return false
			}
		}

		return true
	}

	reversedNum := 0
	temp := n

	for temp > 0 {
		reversedNum = reversedNum*10 + temp%10
		temp /= 10
	}

	left := n
	right := reversedNum

	if left > right {
		left, right = right, left
	}

	total := 0

	for value := left; value <= right; value++ {
		if isPrime(value) {
			total += value
		}
	}

	return total
}

The Go version uses arithmetic digit reversal rather than string manipulation. Starting from the least significant digit, each digit is appended to the reversed number.

The primality test uses the same square root optimization as the Python implementation. Since all values involved are very small, integer overflow is not a concern under the problem constraints.

Worked Examples

Example 1

Input: n = 13

Step 1: Reverse the number

Variable	Value
n	13
r	31

Step 2: Determine range

Variable	Value
left	13
right	31

Step 3: Scan the range

Number	Prime?	Running Sum
13	Yes	13
14	No	13
15	No	13
16	No	13
17	Yes	30
18	No	30
19	Yes	49
20	No	49
21	No	49
22	No	49
23	Yes	72
24	No	72
25	No	72
26	No	72
27	No	72
28	No	72
29	Yes	101
30	No	101
31	Yes	132

Final answer: 132

Example 2

Input: n = 10

Step 1: Reverse the number

Variable	Value
n	10
r	1

Step 2: Determine range

Variable	Value
left	1
right	10

Step 3: Scan the range

Number	Prime?	Running Sum
1	No	0
2	Yes	2
3	Yes	5
4	No	5
5	Yes	10
6	No	10
7	Yes	17
8	No	17
9	No	17
10	No	17

Final answer: 17

Example 3

Input: n = 8

Step 1: Reverse the number

Variable	Value
n	8
r	8

Step 2: Determine range

Variable	Value
left	8
right	8

Step 3: Scan the range

Number	Prime?
8	No

No primes are found, so the answer is:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O((right - left + 1) · √right)	Each number in the range performs a square root primality test
Space	O(1)	Only a few variables are used

The range size is small because the input is at most 1000. Each primality test examines at most √right divisors. No auxiliary data structures proportional to the input size are required.

Test Cases

sol = Solution()

assert sol.sumOfPrimesInRange(13) == 132  # example 1
assert sol.sumOfPrimesInRange(10) == 17   # example 2
assert sol.sumOfPrimesInRange(8) == 0     # example 3

assert sol.sumOfPrimesInRange(1) == 0     # smallest input
assert sol.sumOfPrimesInRange(2) == 0     # range [2,2], prime itself
assert sol.sumOfPrimesInRange(11) == 11   # palindrome prime

assert sol.sumOfPrimesInRange(12) == 28   # range [12,21], primes 13,17
assert sol.sumOfPrimesInRange(20) == 17   # reverse removes trailing zero

assert sol.sumOfPrimesInRange(101) == 101 # palindrome with leading zero after reverse
assert sol.sumOfPrimesInRange(1000) == 76127  # large valid range

Test Summary

Test	Why
n = 13	Standard example with several primes
n = 10	Reverse is smaller due to trailing zero
n = 8	Single-value range with no prime
n = 1	Smallest valid input
n = 2	Single-value range containing a prime
n = 11	Palindromic number
n = 12	Range containing multiple primes
n = 20	Reverse drops leading zero
n = 101	Reverse equals original
n = 1000	Largest constraint value

Edge Cases

Range Contains No Prime Numbers

A range may contain only composite numbers. For example, n = 8 produces the range [8, 8]. A careless implementation might incorrectly treat 1 or other composite values as prime. The is_prime function explicitly rejects values below 2 and checks divisibility correctly, resulting in a sum of 0.

Reverse Is Smaller Than the Original Number

Inputs ending with zero often produce a much smaller reversed value. For example, n = 10 becomes 1. If an implementation assumes the reversed number is always larger, it may iterate over an invalid range. Using min(n, r) and max(n, r) guarantees correct bounds regardless of ordering.

Single-Value Range

When n equals its reverse, the range contains exactly one number. Examples include 8, 11, and 101. The algorithm still works because the inclusive loop processes that single value exactly once and returns either the number itself if it is prime or 0 otherwise.

Numbers Less Than 2

The value 1 is not prime. This is a common source of bugs in primality testing. The helper function immediately returns False for any number below 2, ensuring that 1 is never included in the sum.

Trailing Zeros in the Original Number

Values such as 20, 120, or 1000 reverse to 2, 21, and 1 respectively because leading zeros disappear. The implementation naturally handles this because integer conversion of the reversed representation removes leading zeros automatically, producing the correct interval for prime summation.