leetcode-go/leetcode/hard/233.number-of-digit-one.go

func countDigitOne(n int) (ones int) {
	// Every 1000 has 100 ones at hundreds digit, every 100 has 10 ones at tens digit, ...
	// Assume the base of curr digit (like 1000) is m, then a = n / m, b = n % m,
	// If curr digit is 0, the ones of curr dight is a / 10 * base;
	// curr digit is 1, the ones is a / 10 * base + (b + 1);
	// curr digit is 2~9, the ones is (a / 10 + 1) * base.
	// So, the ones of curr digit is (a + 8) / 10 * base + (a % 10 == 1) * (b + 1)
	for m := 1; m <= n; m *= 10 {
		a, b := n/m, n%m
		ones += (a + 8) / 10 * m
		if a%10 == 1 {
			ones += b + 1
		}
	}
	return
}