counting number of occurrences of digit d

[alirezafz]

Hi
i want to write program that counts number of occurrences of digit d in a given range.
here is my code


it works but the problem is time.it check all numbers which takes so long.
how do i optimize it???

 #include<stdio.h>
int main() {
	int a,b,n,count=0,i,c;
	scanf("%d %d %d",&a,&b,&n);
	for(i=a;i<=b;i++){
		c=i;
		while(c>0){	
			if(n==c%10){
				count++;
				break;
			}		
		c/=10;		
		}
	}
	printf("%d",count);
	return 0;
}

[coder777]

I would suggest to generate all possible combinations of the digit d. Something like this:

00d, 0d0, d00, ... 0dd, d0d, ....

This can be done recursively.

Then check how many of this combination does actually fit within the range. The max amount of digits is determined by the highest number. So first you need to count the amount of digits.

[tpb]

You aren't counting the digits correctly. You shouldn't break out of your digit-counting loop since there may be more matching digits yet to come. Fixing that and running for inputs 0 to 9, 0 to 99, 0 to 999, etc, yields the following pattern. We need to show the 0 digit counts separately since they are different from the other digits. The difference is also shown.

0 up to     1-9       0    diff
-------  ------  ------  ------
      9       1       1       0
     99      20      10      10
    999     300     190     110
   9999    4000    2890    1110
  99999   50000   38890   11110
 999999  600000  488890  111110

If you can write a function that efficiently returns the count of the given digit value from 0 up to x, then you can use it to get the final answer (assuming b >= a):

    answer = count_to(b) - count_to(a + 1);

[lastchance]

#include <iostream>
#include <algorithm>
using namespace std;


//======================================================================


int numdigits( int n, int &power )
{
   int ndigits = 1;
   power = 1;
   int p = 10;
   while ( n >= p )
   {
      ndigits++;
      power = p;
      p *= 10;
   }
   return ndigits;
}


//======================================================================


int cumulative( int target, int n, int ndigits = -1, int power = 1 )
{
   bool start = ndigits < 0;
   if ( start ) ndigits = numdigits( n, power );
   int first = n / power;
   if ( ndigits == 1 ) return ( n >= target );

   int freq;
   if ( target == 0 && start )
   {
      freq = max( first - 1, 0 ) * ( ndigits - 1 ) * power / 10
           + cumulative( target, n % power, ndigits - 1, power / 10 )
           + cumulative( target, power - 1, -1, 1 );
   }
   else
   {
      // Contributions from other than first digit
      freq = first * ( ndigits - 1 ) * power / 10 
           + cumulative( target, n % power, ndigits - 1, power / 10 );

      // Number of occurrences of target as first digit
      if      ( first >  target ) freq += power;
      else if ( first == target ) freq += n % power + 1;
   }

   return freq;
}


//======================================================================


int main()
{
   int a, b, digit;
   cout << "Find number of occurrences of specified digit (0-9) between a and b (inclusive), 0 <= a <= b\n";
   cout << "Input a, b, digit (separated by spaces): ";
   cin >> a >> b >> digit;
   cout << "Number of occurrences of " << digit << " in " << a << " <= x <= " << b << " is ";
   if ( a <= 0 ) cout << cumulative( digit, b ) << '\n';
   else          cout << cumulative( digit, b ) - cumulative( digit, a - 1 ) << '\n';
}

Find number of occurrences of specified digit (0-9) between a and b (inclusive), 0 <= a <= b
Input a, b, digit (separated by spaces): 0 999999 0
Number of occurrences of 0 in 0 <= x <= 999999 is 488890

Find number of occurrences of specified digit (0-9) between a and b (inclusive), 0 <= a <= b
Input a, b, digit (separated by spaces): 0 999999 5 
Number of occurrences of 5 in 0 <= x <= 999999 is 600000

Find number of occurrences of specified digit (0-9) between a and b (inclusive), 0 <= a <= b
Input a, b, digit (separated by spaces): 1234 5678 9 
Number of occurrences of 9 in 1234 <= x <= 5678 is 1284