In this Leetcode Number of Digit One problem solution we have given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Leetcode Number of Digit One problem solution


Problem solution in Python.

class Solution:
    
    def countDigitOne(self, n): # can not deal with n=-1 case!
        if n<=0: return 0
        
        iCount = 0
        iFactor = 1
        iLowerNum, iCurNum, iHigherNum = 0, 0, 0
        
        while n // iFactor != 0:
            iLowerNum = n - (n//iFactor) * iFactor
            iCurNum = (n//iFactor) % 10
            iHigherNum = n //(iFactor * 10)
            
            if iCurNum == 0:
                iCount += iHigherNum * iFactor
            elif iCurNum == 1:
                iCount += iHigherNum * iFactor + (iLowerNum + 1)
            else:
                iCount += (iHigherNum + 1) * iFactor
            iFactor *= 10
        return iCount



Problem solution in Java.

public int countDigitOne(int n) {
       int res = 0;
       long a = 0;
       long b = 0;
       for(long m=1;m<=n;m*=10){
           a = n/m;
           b = n%m;
           if(a % 10 > 1){
               res += a/10 * m + m;
           }else if( a%10 == 1){
               res += a/10 * m + b + 1;
           }else{
               res += a/10 * m;
           }
       }
        return res;
    }


Problem solution in C++.

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)
            return 0;
        int  x = n;
        int y = 0;
        int res = 1;
        
        while(x >= 10)
        {
            res *= 10;
            x /= 10;
            ++y;
        }
        if(x == 1)
            return res / 10 * y +  n % res + 1 + countDigitOne(n % res);
        else
            return res / 10 * (n/res) * y +  res + countDigitOne(n % res);
         
    }
};


Problem solution in C.

int countDigitOne(int n){
    int temp = n, count = 0, rest = 0, coefficient = 0;
    long int step = 1;
    
    for (int i = 0; temp > 0; i++) {
        int digit = temp % 10;
        coefficient = step / 10 * i;
        if (digit > 1) {
            count += digit * coefficient + step;
        } else if (digit == 1) {
            count += coefficient + rest + 1;
        }
        rest += digit * step;
        step *= 10;
        temp /= 10;
    }
    return count;
}