Number of Digit 1 Occurrences

1. Problem Description

Find how many times digit 1 appears among the integers from 1 to 13, and then calculate how many times it appears from 100 to 1300. Counting manually, the numbers containing 1 from 1 to 13 are 1, 10, 11, 12, and 13, for a total of 6 occurrences. Generalize the problem so that the number of 1s appearing in any non-negative integer range can be calculated quickly (the number of 1s from 1 to n).

2. Approach

• Modulo

3. Implementation

func NumberOf1Between1AndN_Solution(n int) int {
	count := 0

	for i := 1; i <= n; i++ {
		j := i
		for j != 0 {
			if j%10 == 1 {
				count++
			}
			j /= 10
		}
	}

	return count
}

4. References

• Number of Digit 1 from 1 to n - NowCoder
• Interview Question 43. Number of Digit 1 from 1 to n - LeetCode
• Number of Digit One - LeetCode