Is Closest Prime Numbers in Range easy or hard?

Closest Prime Numbers in Range is typically classified as a Medium problem. The logic is straightforward once you recognize that generating primes efficiently with the Sieve of Eratosthenes avoids repeated expensive primality checks.

Closest Prime Numbers in Range Python/Java solution

Both Python and Java implementations follow the same logic: either check primality for each number using a sqrt loop or build a sieve array up to the upper bound. After identifying primes, maintain the previous prime and update the pair with the smallest difference.

How to solve Closest Prime Numbers in Range in O(n)?

An O(n) style scan is achieved after preprocessing primes with the Sieve of Eratosthenes. Build the sieve up to the maximum value, then iterate through the range once while keeping track of the previous prime and updating the smallest difference pair.

What is the best approach for Closest Prime Numbers in Range?

The most efficient approach is using the Sieve of Eratosthenes to precompute all primes up to the upper bound of the range. After generating primes, scan from left to right and track the pair with the smallest difference. This runs in O(n log log n) time and avoids repeated primality checks.

Is Closest Prime Numbers in Range asked at Google/Amazon/Meta?

Prime number and number theory problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving prime generation, sieve techniques, or range-based prime queries are common in coding interviews and competitive programming.

What data structure is used in Closest Prime Numbers in Range?

The optimized solution uses a boolean array (or bitset) to represent whether each number is prime in the Sieve of Eratosthenes. The algorithm also tracks the previous prime value while iterating through the range to compute differences.

What is the time complexity of Closest Prime Numbers in Range?

The direct iteration approach checks each number for primality in O(sqrt(n)), giving roughly O((R-L) * sqrt(R)) time. Using the Sieve of Eratosthenes reduces the complexity to O(n log log n) for preprocessing plus O(n) scanning, which is typically faster for large ranges.

Description Hints 2 Solution Video 26:09

2523. Closest Prime Numbers in Range

Medium51.7% acceptance6 companies

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= num1 < num2 <= right .
num1 and num2 are both prime numbers.
num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the minimum num1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Asked at 6 companies

Tiktok

Google Amazon Microsoft Meta Bloomberg

Topics

Math Number Theory

Hints open one at a time

Hint 1

Use Sieve of Eratosthenes to mark numbers that are primes.

Hint 2

Iterate from right to left and find pair with the minimum distance between marked numbers.

26:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution