Share my O(lgn) C++ solution to Number of Digit One


  • 10
    S

    share my O(lgn) solution :

    class Solution {
    public:
    int countDigitOne(int n) {
     	long long base = 1, res = 0, last = 0;
    	while(n >= base){
    		int index = (n / base) % 10;
    		long long remain = n - (n / base) * base;
    		if(index > 1){
    			res = res + index * last + base;
    		}else if(index == 1){
    			res = res + index * last + remain + 1;
    		}else{
    			res = res + index * last;
    		}
    		last = last * 10 + base;
    		base = base * 10;
    	}
    	return res;
    }
    };
    

    Follow Up: you can change the code to meet the new problem Number of Digit K, such as Number of Digit 3

    class Solution {
    public:
    int countDigitK(int n, int k) {
     	long long base = 1, res = 0, last = 0;
    	while(n >= base){
    		int index = (n / base) % 10;
    		long long remain = n - (n / base) * base;
    		if(index > k){
    			res = res + index * last + base;
    		}else if(index == k){
    			res = res + index * last + remain + 1;
    		}else{
    			res = res + index * last;
    		}
    		last = last * 10 + base;
    		base = base * 10;
    	}
    	return res;
    }
    };

  • 0
    J

    Why the variable type of 'base' ,'res','last' must use long long? In the meanwhile the input variable type is int.


  • 0
    S

    @John Actually, only the variable type of 'base' must be long long. For example, if the n == INT_MAX, the value of base can be 10,000,000,000, which is overflow when base is int, so the judgement of while(n >= base) will be wrong.


  • 0
    L

    I guess it's better to change "remain = n - (n / base) * base" to "remain = n % base".


  • 0
    S

    @ ljian3377 Yeah, that looks like more simple


  • 0
    M

    can anyone explain the logic behind it


  • 0
    R

    why "last = last * 10 + base" ?


  • 0
    R

    did you know yet why last=last*10 +base


Log in to reply
 

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