c++ - How make this even count code faster? -

the following code meant find total numbers between l , r product of digits (for multiple test cases t). code runs extremely slow r greater 100000. can suggest better alternative?

#include <iostream> #include <algorithm> using namespace std; long long int nd(long long int x, int n) //return digit @ particular index    staring 0 index unit place { while (n--) {     x /= 10; } return (x % 10); } int ng(long long int number) //returns total number of digits in integer { int digits = 0; if (number < 0) digits = 1; while (number) {     number /= 10;     digits++; } return digits; }  int main() { int t; cin>>t; long long int l[t], r[t], c; for(long long int j=0;j<t;j++) {     cin>>l[j]>>r[j]; } for(long long int k=0;k<t;k++) {       long long int sum=0;   long long int t=0;    for(long long int i=l[k];i<=r[k];i++)   {    while(t<ng(i))    {        c=nd(i,t);        if((c%2)==0)        {            ++sum;            break;        }        ++t;     }    t=0;       }  cout<<sum<<endl; }     cin.ignore(); cin.get(); return 0; }             

all numbers starting with, e.g., 10…, 12…, 14…, …, 2…, 30…, known have product of digits. therefore start left (more significant digits) , count in blocks. there few numbers product of digits odd (such 1111111111), here have dig deeper.

here pseudocode:

int count(string prefix, int digits) {   int result = 0;   if (digits == 0)     return 0;   (int d = 0; d < 10; d++) {     if (d%2 == 0)       result += 10**(digits-1);     else       result += count(prefix . tostring(d), digits-1);   }   return result; } 

this called count("2", 8) count interval 200000000 299999999.

---

here haskell implementation whole block (i.e., d-digit numbers):

blockcount :: integer -> integer blockcount 0 = 0 blockcount d = 5 * 10^(d-1) + 5 * blockcount (d-1) 

e.g., blockcount 1000 calculated 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999066736381496781121009910455276182830382908553628291975378285660204033089024224365545559672902118897640405010069675757375784512478645967605158479182796069243765589333861674849726004924014098168488899509203734886881759487485204066209194821728874584896189301621145573518880530185771339040777982337089557201543830551112852533471993671631547352570738170137834797206804710506392882149336331258934560194469281863679400155173958045898786770370130497805485390095785391331638755207047965173135382342073083952579934063610958262104177881634921954443371555726074612482872145203218443653596285122318233100144607930734560575991288026325298250137373309252703237464196070623766166018953072125441394746303558349609375 in less second.

you’d still have add code breaks range suitable blocks.