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
Yes, even if there are 10^6 queries of range, it won’t give TLE 
A better idea to store all good numbers (there are only 10^6 good numbers),then do binary search for each query
max digit will be 7 (20 characters )
1 Like
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)
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
Ok …but mera 1st point ko solve kro…Kya hame sum of digit krna hi padega kya
Sare good no. Less than r right
Yes…for sure… …(20…chars…)
Hame har ek no. Ka sum of digit krne me log10(n) lagnege right
Do this:-
Store every good number less than 10^7 in array ‘b’ .
Size of array ‘b’ will be something around 10^6.
Now, for each query, read l and r. Do binary search for ‘l’ and ‘r’ in array ‘b’ and u get the count of good numbers from 1 to l and 1 to r, say x and y, answer is y-x
Are bhai jitne digit has, 6 or 7, O(6) lagega per number , zyaada socho mat.
Ha ye to aagya… 20 char
Acchaa…ha vo bhi…
Or agar range 10^18 ho to
17*81 tk prime store karvau…hna
Really…
Then it will be okay 
Yeah but when b-a is small it will be dominant.
So I kept it.
Even then it doesn’t matter as 567.log… is too small 
1 Like
Still I won’t discard it from formal complexity
Step 1: The upper bound for the number is 9999999. Thus, the “maximum possible prime” for sum of squares = 7*81 = 567. Lets calculate all primes from 1 to 567. Store it in a set. Or even better, build a boolean array (568 bits)
Step 2: For i in range: calculate sum of digits, is it in the set (or check if boolean array at index “sum” is 1 or 0? If yes, calculate sum of square of digits, is it in the set? If it is - add it to output vector.
This is an O(n) algorithm - considering that building list of primes till 567 will take trivial time.