# C++ template for count any digit in a num range, clean and straight forward

• Brutal force solution is to count digits num by num, while optimal solution is to count digits digit by digit with increasing weight, i.e. weight = 1, 10, 100, 1000

``````    int CheckOccurrence(int n, int d) {
// we will example  n = 3726,  d = 3
int weight = 1, count = 0, curr = n;
while(curr > 0) {
// every iteration is a discussion based on current digit = d

//case 1: prefix=[0,371] + set current digit=d + suffix=[0,weight-1]。 note there are 372 numbers in [0,371] i.e. curr / 10

count += ( curr/10 - (d == 0) ) * weight;  //  number of choices for prefix * number of choices for suffix.   NOTE: if current digit = d = 0, then prefix should not be 0, that is why we reduce 1 from curr/10.

//case 2. current actual digit > d, prefix=372 + set current digit=d + suffix=[0,weight-1]
if(curr % 10 > d) {
count += weight;
}
// case 3. current actual digit > d, prefix=372 + set current digit=d + suffix=[0,n%weight]
else if(curr % 10 == d) {
count += n % weight + 1;
}

curr /= 10; // move to next digit with larger weight.
weight *= 10;
}
return count;
}

int countDigitOne(int n) {
return CheckOccurrence(n, 1);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.