LeetCode-in-Java
233. Number of Digit One
Hard
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0
Constraints:
0 <= n <= 109
Solution
@SuppressWarnings("java:S127")
public class Solution {
public int countDigitOne(int n) {
int ans = 0;
// count total number of 1s appearing in every digit, starting from the last digit
for (int k = n, cum = 0, curr10 = 1; k > 0; curr10 *= 10) {
int rem = k % 10;
int q = k / 10;
if (rem == 0) {
ans += q * curr10;
} else if (rem == 1) {
ans += q * curr10 + cum + 1;
} else {
ans += (q + 1) * curr10;
}
k = q;
// if loop is at 3rd last digit and n = 54321, cum is now = 321
cum += rem * curr10;
}
return ans;
}
}