Share my readable C++ and python Simple Solution with only 0ms and 36ms


  • 0
    S
    • compute a list with the number of 1s less than the power of 10
    • for example:
    • in C++, I build a vector:{0: 0, 1: 0, 10: 1, 100: 20, 1000:
      300},means that there are 300 1s less than pow(10,3)
    • in Python, I built a dict that {0: 0, 1: 0, 10: 1, 100: 20, 1000:
      300},means that there are 300 1s less than 1000

    My C++ Solution:

        int countDigitOne(int n) {
            if (n <= 0)
            	return 0;
            int bits = 0, res = 0;
            
            while(n >= pow(10,bits))
            	bits ++;
            vector<int>flag(bits,0);
            for(int i=1;i < bits; i++)
            	flag[i] = flag[i-1]*10 + pow(10,i-1);
            int temp = pow(10,bits-1);
    		while(n >= 10){
    			int foo = n/temp;
    			if (foo > 1)
    				res += temp;
    			else if(foo == 1)
    				res += (n%temp + 1);
    			res += foo * flag[bits-1];
    			bits --;
    			n = n % temp;
    			temp = temp/10;
    		}
    		if(n>=1)
    			res ++;
    		return res;
        }
    

    My Python Solution:

        def countDigitOne(self, n):
            bits = 0
            dic = {0:0,1:0,10:1}
            res = 0
            if n <= 0:
                return 0
            while n >= 10**bits:
                bits += 1
            temp = 10**(bits - 1)
            for i in range(1,bits):
                dic[10**i] = dic[10**(i - 1)] * 10 + 10**(i-1)
            print dic
            while n >= 10:
                x = n/temp
                if x > 1:
                    res += (temp)
                elif x == 1:
                    res += (n % temp +1)
                res += x*(dic[temp])
                n = n % temp
                temp /= 10
            if n >= 1:
                res += 1
            return res

Log in to reply
 

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