Efficient Java Solution to Count Digit 1 Occurrences from 1 to n

The author begins by emphasizing that a high salary is meaningless without real value, arguing that fast reaction and solid fundamentals are more important for new engineers than simply writing lots of code or solving typical interview puzzles.

In a real work scenario, a sudden report error about the count of digit 1 prompted the author to revisit a classic interview problem: given an integer n, determine how many times the digit 1 appears in the decimal representation of all numbers from 1 to n.

While a naïve solution would convert each number to a string and count, this approach becomes infeasible for large n. The author therefore applies a digit‑by‑digit (positional) method that processes the number in three parts: high (digits to the left of the current position), cur (the current digit), and low (digits to the right).

The rule is:

If cur == 0, the count contributed by this position is high * factor.

If cur == 1, the count is high * factor + (low + 1).

If cur > 1, the count is (high + 1) * factor.

Here factor represents the weight of the current digit (1, 10, 100, …). The algorithm iterates while n / factor != 0, updating low, cur, high and accumulating the answer.

public class CountDigitOne {
    // Count digit '1' occurrences from 1 to n
    public static long countDigitOne(long n) {
        if (n <= 0) return 0;
        long ans = 0;
        long factor = 1; // 1,10,100...
        while (n / factor != 0) {
            long low = n % factor;
            long cur = (n / factor) % 10;
            long high = n / (factor * 10);
            if (cur == 0) {
                ans += high * factor;
            } else if (cur == 1) {
                ans += high * factor + (low + 1);
            } else {
                ans += (high + 1) * factor;
            }
            factor *= 10;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(countDigitOne(13)); // 1..13 => 6
        System.out.println(countDigitOne(100)); // 1..100 => 21
        System.out.println(countDigitOne(0)); // 0
    }
}

Running the program confirms the expected results: for n = 13 the count is 6 (numbers 1, 10, 11, 12, 13 each contain a 1), and for n = 100 the count is 21. The author notes that such precise counting is crucial in production reporting, where a single mistake can lead to extensive follow‑up inquiries.