Number Of Digit One Problem


Description

LeetCode Problem 233.

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:

1
2
Input: n = 13
Output: 6

Example 2:

1
2
Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10^9


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    // Basic idea: count number of combination of 1 at each digit in two cases: prefix appears or not
    // Eg.3101592:
    // 1) one at hundreds:      1 (< 5): [1~3101]1[0~99]. So # = 3101 * 100 + 100 (Safe since 31011XX never be greater than 31015XX)
    // 2) one at thousands:     1 (= 1): [1~310]1[0~592]. So # = 310 * 1000 + (592 + 1) (Unsafe if prefix is 0, it must be <= 1592)
    // 3) one at ten thousands: 1 (> 0): [1~30]1[0~9999]. So # = 30 * 10000 (If prefix is 0, no 1 digit number exist)
    int countDigitOne(int n) {
    int ones = 0;
    for (long long m = 1; m <= n; m *= 10) {
        int a = n / m, b = n % m;
        ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
    }
    return ones;
}
};




Related Posts

Beautiful Arrangement II Problem

LeetCode 667. Given two integers n and k, construct a...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Perfect Number Problem

LeetCode 507. A perfect number is a positive integer that...

Optimal Division Problem

LeetCode 553. You are given an integer array nums. The...

Minimum Time Difference Problem

LeetCode 539. Given a list of 24-hour clock time points...

Minimum Moves To Equal Array Elements Problem

LeetCode 453. Given an integer array nums of size n,...