Sum of Primes Between Number and Its Reverse solution and explanation
7 more videos on this problem
weekly contest 500 | leetcode 3917 | leetcode 3918 | leetcode 3919 | leetcode 3920 | Easy solutionsCode With Vick · 41:57 · 567 views
Leetcode 3918|Sum of Primes Between Number and Its Reverse|Weekly Contest 500|Sieve of EratosthenesAsmita Mhetre · 9:21 · 156 views
3918. Sum of Primes Between Number and Its ReverseAlgoVision with Saheb · 19:07 · 146 views
Sum of Primes Between Number and Its Reverse | Leetcode 3918 | Explanation With Code | Javacodewithsitaram · 21:17 · 35 views
LeetCode 3918 | Sum of Primes Between Number and Its Reverse 🔁 Prime Range Intuition | Java⚡Dev Den · 18:48 · 29 views
LeetCode Problem 3918 | Sum of Primes Between Number and Its ReverseRepovive TV · 4:17 · 20 views
Sum of Primes Between Number and Its Reverse | 2 methods | Leetcode weekly contest 500 | #3918UMANG AGRAWAL · 15:33 · 19 views
LeetCode 3918 | Sum of Primes Between Number and Its Reverse | Easy C++ SolutionProjectForge · 11:02
The problem
You are given an integer n.
Let r be the integer formed by reversing the digits of n.
Return the sum of all prime numbers between min(n, r) and max(n, r), inclusive.
Example 1:
Input: n = 13
Output: 132
Explanation:
- The reverse of 13 is 31. Thus, the range is
[13, 31]. - The prime numbers in this range are 13, 17, 19, 23, 29, and 31.
- The sum of these prime numbers is
13 + 17 + 19 + 23 + 29 + 31 = 132.
Example 2:
Input: n = 10
Output: 17
Explanation:
- The reverse of 10 is 1. Thus, the range is
[1, 10]. - The prime numbers in this range are 2, 3, 5, and 7.
- The sum of these prime numbers is
2 + 3 + 5 + 7 = 17.
Example 3:
Input: n = 8
Output: 0
Explanation:
- The reverse of 8 is 8. Thus, the range is
[8, 8]. - There are no prime numbers in this range, so the sum is 0.
Constraints:
1 <= n <= 1000
Approach overview
Problem Overview: You are given an integer n. Reverse its digits to get another number rev. The task is to compute the sum of all prime numbers in the range between min(n, rev) and max(n, rev). The main challenge is efficiently identifying primes across that range.
Approach 1: Brute Force Primality Check (O(k * sqrt(k)) time, O(1) space)
Compute the reversed value of n, then determine the interval [L, R] where L = min(n, rev) and R = max(n, rev). Iterate through every number in this range and run a primality test for each value. A typical check tries dividing the number by all integers from 2 to sqrt(x). If no divisor is found, add it to the running sum. This method is straightforward and works well when the interval is small, but repeated square‑root checks make it slow for larger ranges.
Approach 2: Precompute Using Sieve of Eratosthenes (O(R log log R) time, O(R) space)
Instead of checking each number independently, generate all primes up to R using the Sieve of Eratosthenes. Create a boolean array where each index represents whether the number is prime. Start from 2, mark multiples as composite, and continue until sqrt(R). Once the sieve is built, iterate from L to R and sum values whose sieve entry is still marked prime. This avoids repeated factor checks and dramatically improves performance when the range is large. The sieve approach is a classic technique from number theory and math problems involving repeated prime queries.
Approach 3: Segmented Sieve for Large Ranges (O((R-L+1) log log R) time, O(R-L+1) space)
If R can be extremely large but the interval size (R-L) is manageable, a segmented sieve becomes more memory efficient. First compute primes up to sqrt(R). Then create a local boolean array representing only the interval [L, R]. Use the previously computed primes to mark multiples within this segment. Remaining unmarked numbers are prime and can be summed directly. This method avoids allocating a full sieve up to R and is commonly used in competitive programming when dealing with big numeric ranges.
Recommended for interviews: The Sieve of Eratosthenes approach is typically the expected solution. Starting with the brute force method shows you understand primality testing, but moving to the sieve demonstrates stronger algorithmic thinking and familiarity with efficient prime generation techniques. It reduces repeated work and keeps the runtime near linear relative to the range size.
Solution
We note that the reversed number r of n will not exceed 1000, so we can precompute all prime numbers up to 1000.
Next, we compute low = min(n, r) and high = max(n, r), then iterate through all integers in the range [low, high]. If an integer is prime, we add it to the answer.
The time complexity is O(n), and the space complexity is O(M), where M is the upper bound used for prime precomputation, which is 1000 here.
limit = 1000
is_prime = [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 j in range(i * i, limit + 1, i):
is_prime[j] = False
class Solution:
def sumOfPrimesInRange(self, n: int) -> int:
r = int(str(n)[::-1])
low = min(n, r)
high = max(n, r)
return sum(x for x in range(low, high + 1) if is_prime[x])class Solution {
private static final int LIMIT = 1000;
private static final boolean[] isPrime = new boolean[LIMIT + 1];
static {
for (int i = 0; i <= LIMIT; i++) {
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= LIMIT; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= LIMIT; j += i) {
isPrime[j] = false;
}
}
}
}
public int sumOfPrimesInRange(int n) {
int r = Integer.parseInt(new StringBuilder(String.valueOf(n)).reverse().toString());
int low = Math.min(n, r);
int high = Math.max(n, r);
int ans = 0;
for (int x = low; x <= high; x++) {
if (isPrime[x]) {
ans += x;
}
}
return ans;
}
}const int MX = 1000;
bool isPrime[MX + 1];
auto init = [] {
for (int i = 0; i <= MX; ++i) isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= MX; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= MX; j += i) {
isPrime[j] = false;
}
}
}
return 0;
}();
class Solution {
public:
int sumOfPrimesInRange(int n) {
int r = 0;
int tmp = n;
while (tmp) {
r = r * 10 + tmp % 10;
tmp /= 10;
}
int low = min(n, r);
int high = max(n, r);
int ans = 0;
for (int x = low; x <= high; ++x) {
if (isPrime[x]) ans += x;
}
return ans;
}
};const LIMIT = 1000;
const isPrime: boolean[] = new Array(LIMIT + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= LIMIT; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= LIMIT; j += i) {
isPrime[j] = false;
}
}
}
function sumOfPrimesInRange(n: number): number {
const r = parseInt(n.toString().split('').reverse().join(''));
const low = Math.min(n, r);
const high = Math.max(n, r);
let sum = 0;
for (let x = low; x <= high; x++) {
if (isPrime[x]) sum += x;
}
return sum;
}var isPrime [1001]bool
func init() {
for i := 0; i <= 1000; i++ {
isPrime[i] = true
}
isPrime[0], isPrime[1] = false, false
for i := 2; i*i <= 1000; i++ {
if isPrime[i] {
for j := i * i; j <= 1000; j += i {
isPrime[j] = false
}
}
}
}
func sumOfPrimesInRange(n int) (ans int) {
r := 0
for x := n; x > 0; x /= 10 {
r = r*10 + x%10
}
low := min(n, r)
high := max(n, r)
for x := low; x <= high; x++ {
if isPrime[x] {
ans += x
}
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Primality Check | O(k * sqrt(k)) | O(1) | Small ranges where direct prime checks are cheap |
| Sieve of Eratosthenes | O(R log log R) | O(R) | General case when R is moderate and multiple primes must be checked |
| Segmented Sieve | O((R-L+1) log log R) | O(R-L+1) | Very large upper bounds where allocating a full sieve up to R is impractical |
Frequently asked questions
Is Sum of Primes Between Number and Its Reverse easy or hard?
The problem is generally classified as Medium because it combines two ideas: reversing an integer and efficiently computing primes in a numeric range. Developers familiar with sieve techniques can implement the optimal solution quickly.
Sum of Primes Between Number and Its Reverse Python/Java solution
Both Python and Java implementations typically compute the reversed integer, run a Sieve of Eratosthenes up to the maximum value, and iterate through the interval to accumulate primes. The core logic is identical across languages: sieve construction followed by a linear scan.
How to solve Sum of Primes Between Number and Its Reverse in O(n)?
A near‑linear solution uses the Sieve of Eratosthenes. Build a prime sieve up to the larger value between the number and its reverse, which takes O(n log log n). Then iterate through the required range and accumulate primes using constant‑time lookups from the sieve array.
What is the best approach for Sum of Primes Between Number and Its Reverse?
The Sieve of Eratosthenes is the most practical solution. Compute the reversed value of the number, determine the range [L, R], generate primes up to R using a sieve, then sum primes within the interval. This avoids repeated primality checks and runs in O(R log log R) time.
Is Sum of Primes Between Number and Its Reverse asked at Google/Amazon/Meta?
Variants of prime range queries and number reversal problems appear in interviews at large tech companies. While the exact problem title may vary, companies like Amazon and Google frequently test number theory basics such as primality testing and sieve-based optimizations.
What data structure is used in Sum of Primes Between Number and Its Reverse?
The optimal approach uses a boolean array (or bitset) to represent a sieve of primes. Each index indicates whether the number is prime, enabling constant-time checks when summing primes within the computed range.
What is the time complexity of Sum of Primes Between Number and Its Reverse?
The brute force approach that checks primality for each number runs in about O(k * sqrt(k)), where k is the size of the interval. The optimized sieve solution runs in O(R log log R) time with O(R) space, which is significantly faster for larger ranges.