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.
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; }
0 Comments