Given a range find total no. In a range such that the sum of digit and sum of square of digit is prime

help
,
1

This question is asked in one of my friends interview :::
Given a range find total no. In a range such that the sum of digit and sum of square of digit is prime.
Range (a,b) a and b less than 10^7
I am trying sieve approach to store all primes and compute sum of digit and sum of square of digit of each no. And check whether they are prime or not. If yes then count .
Complexity (nlog(log n) + nlog(d))
Can anyone solve this by some approach or efficiently ,…
@anon55659401 @l_returns @ashokshaun @vijju123 @samarthtandon @aryanc403

1 Like
2

Solution is digit-dp for sure, but can you atleast give 1 example of a number??

3

Ex 23
2+3 is 5
4+9 is 13 both prime

4

Say, a=1 and b=10^7(worst case).
Traverse from 1 to 10^7…and total time complexity:-7(10^7) which will work under 1 second. Dont do any seive as:-
999999=81*6=486(is the largest number you can get, so u only have to find prime numbers till 500 only :slight_smile: )

1 Like
5

What that mean I don’t understand…

6

Why 486 is largest no.if u make a program this will help me

7

567*
10^7 has 8 digits and all values less than that will have 7 digits.
See @ssrivastava990 almost all numbers can have at most 7 digits.
Each digits can be 9 at most.
Hence max prime will be 9*9*7.
So it’s O(b-a + 567*log(log(567))

1 Like
8

Code with worst case range :- CkdwRP - Online C++0x Compiler & Debugging Tool - Ideone.com(Never use my code to find prime numbers, if u do, then mention the source in Codechef contests or else…you…know…what will happen…)
(Works under 1 sec. :slight_smile: )

1 Like
9

Yup, I fortunately used 600 as the upper limit, I am so lucky even after being noob at math lol .

10

I guess, 567log()… part should be ignored as it is insignificant… Complexity is very near to 7(b-a) or 6(b-a)… Am I correct ?

11

For multiple query, take prefix sum over 1 to 1e7, and answer query :slight_smile:

1 Like
12

Great, but I fear, that doing prefix sum till 10^7 th element in the array may cause some problem… ? :sweat_smile::sweat_smile::sweat_smile:

16

One i did but it take large memory, for me i would not prefer it :slight_smile:

17

Global declaration may help… :slight_smile:

18

Suno me ye bol rha hu ki ye prime sieve to optimize kr di par Kya har ek no.ke liye sum of digit nikalana efficient h…

1 Like
19

Yes, even if there are 10^6 queries of range, it won’t give TLE :slight_smile:

20

A better idea to store all good numbers (there are only 10^6 good numbers),then do binary search for each query :slight_smile:

21

max digit will be 7 (20 characters )

1 Like
22

No … Let’s suppose if there is range 2, 475688 now we have to sum of each digit of sum of square of each digit and check , is there is any need to sum of digit or sum of square of digit…

Yes if there are multiple queries we store count in prefix array and return pref(b)-pref(a-1)

23

Prefix array will take too much time, risks of tle…if all program is combined…better use binary search on good numbers array of length 10^6 for each query :slight_smile: