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


  • 0
    C

    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);
        }
    

Log in to reply
 

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