Prime Digit Sum

Hard
0/120
Average time to solve is 45m
profile
Contributed by
4 upvotes
Asked in companies
OracleCodenationTCS

Problem statement

Find the number of good numbers between two numbers ‘L’ and ‘R’ inclusive. A number is good if the sum of its digits is a prime number

Output the number of good numbers.

Example : 
Input:
'L' = 15 and 'R' = 19
There is only 1 number between which is good,
16 = 1 + 6 = 7 (which is a prime number).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two integers ‘L’ and ‘R’.
Output format : 
For each test case, output a single integer denoting the number of good numbers between ‘L’ and ‘R’.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function. 1 is a co-prime number.
Constraints : 
1 <= ‘T’ <= 10 
1 <= ‘L’, ‘R’ <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
5 11
1 20
Sample Output 1 :
3
9
Explanation Of Sample Input 1 :
For test case 1 we have, 

5 , 7 ,
11 = 1+1 = 2
As 2, 5, 7 are prime numbers so 5, 7, 11 are good.

For test case 2 we have,

2, 3, 5, 7,
11 = 1 + 1 = 2
12 = 1 + 2 = 3
14 = 1 + 4 = 5   
16 = 1 + 6 = 7
20 = 2 + 0 = 2
As 2, 3, 5, 7 are prime numbers so 2, 3, 5, 7, 11, 12, 14, 16, 20 are good.
Sample Input 2 :
2
12 16
9 19
Sample Output 2 :
3
4
Hint

Can you try Brute Force?

Approaches (2)
Brute Force

Approach : 

  1. Precalculate the prime numbers from 0 to 200 by ‘SeiveOfEratosthenes’.
  2. Traverse from each integer from ‘L’ to ‘R’ and for each integer, i find the sum of digits of i.
  3. Check if the sum is prime and increase the result accordingly.
     

Algorithm : 
 

  • Create and initialize array ‘PRIME[200]’ as true
  • Using ‘SeiveOfEratosthenes’ we mark prime numbers in the array ‘PRIME’
  • Create a ‘RES’ variable to store the count of good numbers
  • Run a For loop from i = ‘L’ to ‘R’
    • Find the sum of digits of i and if the sum is prime increase the result by 1.
  • Return ‘RES’
Time Complexity

O(digits * (R - L + 1)), where ‘L’ and ‘R’ are left and right bounds of range, ‘digits’ is the number of digits in ‘R’.
 

Traversing from ‘L’ to ‘R’ takes ~(R - L) and for each integer between ‘L’ and ‘R’ we check for each sum in ~digits.

Hence the overall time complexity is O(digits * (R - L + 1)).

Space Complexity

O(M), Where M = 200.
 

The prime array takes ~200 space and ‘res’ variable takes ~1 space. 

Hence, the overall Space Complexity is O(M).

Code Solution
(100% EXP penalty)
Prime Digit Sum
Full screen
Console