Kth Prime Sum | Practice Problems

Kth Prime Sum

★★★★★

2 votes

, Algorithms, Dynamic Programming, Binary Search, Number theory

Details

Submissions

Discussion

Editorial

Problem

We are given $Q$ queries in the form of " $L \space R \space K$ ".
For each query you are asked to print the $k^{th}$ smallest number in the range $L$ to $R$ (both inclusively) whose digit sum is a prime number or report (print $-1$ ) if it doesn't exist.

Input Format

First line of input contains an integer $Q$ .
Next $Q$ lines contain three space-separated integers $L \space R \space K$ denoting the query.

Output Format
For each $i^{th}$ query, print a single integer denoting the answer to the $i^{th}$ query.

Constraints
$1 \le Q \le 500$
$1 \le L \le R \le 10^{18} \\1 \le K \le R - L + 1$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

For the first query: The numbers in the range are $[3, 4, 5, 6, 7]$ in which $3, 5$ and $7$ are having the digit sum a prime and $2nd$ of them is $5$ so we will output $5$ .

For the second query: There is only one number in the range $[6]$ in which none is having the digit sum a prime and $1st$ of them deesn't exist so we will output $-1$ .

For the third query: The numbers in the range are $[10, 12, 13, 14, 15 ... 100]$ in which $[11, 12, 14, 16, 20, 21, 23, 25, 29, 30, 32, 34, 38, 41,43, ... 98]$ are having the digit sum a prime and $15th$ ot them is $43$ so we will output $43$ .