Skip to main content

Number of Digit One

Problem​

Given an integer n, count the total number of digitdigit 1 appearing in all non-negative integers less than or equal to n.

Examples​

Example 1:

Input: n = 13

Output: 6

Example 2:

Input: n = 0

Output: 0

Constraints​

  • 0 <= n <= 10^9

Approach​

There are four approaches discussed that helps to obtain the solution:

  1. Dynamic Programming Table:

    • Initialize 'count' to 00, which will store the total count of 1′s1's.

    • Use 'factor' to isolate each digit position, starting from the units place and moving to higher places (tens, hundreds, etc.).

  2. Iterative Analysis:

  • Loop through each digit position using 'factor', which starts from 11 and increases by a factor of 1010 in each iteration.

  • For each position defined by 'factor', determine:

    • 'lowerNumbers': Numbers to the right of the current digit.

    • 'currentDigit': The digit at the current position.

    • 'higherNumbers': Numbers to the left of the current digit.

  1. Count Calculation:

    • If 'currentDigit' is 00, then the count of 1′s1's contributed by the current digit position comes solely from higher numbers.

    • If 'currentDigit' is 11, it includes all 1′s1's contributed by higher numbers, plus the 1′s1's in the lower numbers up to 'lowerNumbers + 1'.

    • If 'currentDigit' is greater than 11, it includes all 1′s1's contributed by higher numbers and the full set of lower numbers for that digit position.

  2. Result:

    • Return the accumulated 'count' after processing all digit positions.

Solution for Number of Digit One​

This problem can be solved using dynamic programming. The problem requires to count the total number of digit 11 appearing in all non-negative integers less than or equal to n.

Code in Java​

class Solution {
public int countDigitOne(int n) {
if (n <= 0) return 0;

int count = 0;
for (long factor = 1; factor <= n; factor *= 10) {
long lowerNumbers = n - (n / factor) * factor;
long currentDigit = (n / factor) % 10;
long higherNumbers = n / (factor * 10);

if (currentDigit == 0) {
count += higherNumbers * factor;
} else if (currentDigit == 1) {
count += higherNumbers * factor + lowerNumbers + 1;
} else {
count += (higherNumbers + 1) * factor;
}
}

return count;
}

public static void main(String[] args) {
Solution sol = new Solution();

// Test cases
System.out.println(sol.countDigitOne(13));
System.out.println(sol.countDigitOne(0));
}
}

Complexity Analysis​

Time Complexity: O(log10n)O(log_{10} n)​

Reason: The time complexity is O(log10n)O(log_{10} n), because we are processing each digit position from the least significant to the most significant, and the number of digit positions is logarithmic relative to the input size.

Space Complexity: O(1)O(1)​

Reason: The space complexity is O(1)O(1), because we only use a constant amount of extra space regardless of the input size.

References