Welcome to Subscribe On Youtube

3918. Sum of Primes Between Number and Its Reverse

Description

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

Solutions

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.

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.

  • 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;
    }
};


  • 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])


  • 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
}


  • 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;
}

All Problems

All Solutions