Solution For Number Of Digit One

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

Example:

Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution:

Approach: The problem can be solved using mathematics calculations and a bit of observation. We will be using a digit by digit approach to count the number of ones.

Step 1: Convert the given number to a string to examine each digit in the number.

Step 2: We need to calculate the number of ones in each digit place (1s, 10s, 100s, etc.) separately.

Step 3: We will consider the example of the number 3456. For the 1s place, we will use the following formula: (345/10)1 + min(max(345%10 – 1 + 1, 0), 1) = (34)1 + min(max(5 – 1 + 1, 0), 1) = 34+1 = 35.

• We divide 345 by 10 to get the quotient 34, which tells us how many times the digit one appears in the 1s place for the numbers less than or equal to 345.

• The min(max(345%10 – 1 + 1, 0), 1) gives us the extra ones that appear in the number 345 specifically.

• 345%10 gives us the digit in the 1s place, which is 5.

• We subtract 1 from it, so we can count the ones less than or equal to the digit in the 1s place.
• We then add 1 to the result to count the ones at the digit in the 1s place itself, but only if this result is less than 2, otherwise we only count 1.

Step 4: Similarly, for the 10s place, we will use the following formula: (34/10)*10 + min(max(34%10 – 1 + 1, 0), 10) = 30 + 5 = 35.

• We divide 34 by 10 to get the quotient 3, which tells us how many times the digit one appears in the 10s place for the numbers less than or equal to 345.

• The min(max(34%10 – 1 + 1, 0), 10) gives us the extra ones that appear in the number 345 specifically.

• 34%10 gives us the digit in the 10s place, which is 4.

• We subtract 1 from it, so we can count the ones less than or equal to the digit in the 10s place (i.e., number of ones in the “10s” multiples).
• We then add 1 to the result to count the ones at the digit in the 10s place itself.

Step 5: We continue this process for each digit place (100s, 1000s, etc.) until we have counted all the ones in the number.

Step 6: Add up all the ones we’ve counted to get the total number of ones.

Code implementation:

class Solution:
def countDigitOne(self, n: int) -> int:
count, factor = 0, 1
while factor <= n:
count += (n // (factor * 10)) * factor + min(max(n % (factor * 10) - factor + 1, 0), factor)
factor *= 10
return count

Time Complexity: The time complexity of the above solution is O(logn).

Space Complexity: The space complexity of the above solution is O(1).

Step by Step Implementation For Number Of Digit One

public class Solution {
    public int countDigitOne(int n) {
        if (n <= 0)
            return 0;
 
        // split integer into: xxxxyyyzzz
        int x = n / 1000000000;
        int y = (n / 1000000) % 1000;
        int z = (n / 1000) % 1000;
        int w = n % 1000;
 
        // count of 1s on every level
        int count = 0;
 
        // count of 1s on every level in xxxxyyyzzz
        count += countDigitOne(x);
        count += countDigitOne(y);
        count += countDigitOne(z);
 
        // count of 1s on every level in w
        count += countDigitOne(w);
 
        // count of 1s on every level in xxxxy
        count += x * 100000000;
 
        // count of 1s on every level in xxxxyyy
        count += y * 1000000;
 
        // count of 1s on every level in xxxxyyyzz
        count += z * 1000;
 
        // count of 1s on every level in xxxxyyyzz1~999
        count += (w + 1) * countDigitOne(999);
 
        return count;
    }
}

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

# Example:

# Input: 13
# Output: 6 
# Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

# Solution:

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0
        count = 0
        for i in range(1, n+1):
            count += self.helper(i)
        return count
    
    def helper(self, i):
        count = 0
        while i > 0:
            if i % 10 == 1:
                count += 1
            i //= 10
        return count

var countDigitOne = function(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        let div = i;
        while (div > 0) {
            if (div % 10 === 1) {
                count++;
            }
            div = Math.floor(div / 10);
        }
    }
    return count;
};

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        for (long long i = 1; i <= n; i *= 10) {
            long long divider = i * 10;
            count += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
        }
        return count;
    }
};

/*
We can solve this problem by breaking it down into subproblems.

For each position i in the number n, we can find out how many numbers have 1 in that position by looking at the digit to the left and the digit to the right of position i.

If the digit to the right of position i is not 0, then we know that there will be (n / (i * 10)) * i numbers that have 1 in position i.

For example, if n = 1234, then for position i = 1, we know that there will be (1234 / (1 * 10)) * 1 = 234 numbers that have 1 in position 1.

If the digit to the right of position i is 0, then we must look at the digit to the left of position i to see if there are any numbers with 1 in position i.

If the digit to the left of position i is not 0, then we know that there will be ((n / (i * 10)) + 1) * i numbers that have 1 in position i.

For example, if n = 1234, then for position i = 2, we know that there will be ((1234 / (2 * 10)) + 1) * 2 = 111 numbers that have 1 in position 2.

If the digit to the left of position i is 0, then we know that there will be (n / (i * 10)) * i numbers that have 1 in position i.

For example, if n = 1234, then for position i = 3, we know that there will be (1234 / (3 * 10)) * 3 = 20 numbers that have 1 in position 3.

We can use these observations to write a simple algorithm to solve the problem.
*/

using System; 

public class Solution {
    public int CountDigitOne(int n) {
        int count = 0;
        for (long k = 1; k <= n; k *= 10)
        {
            long r = n / k, m = n % k;
            // sum up the count of ones on every place k
            count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return count;
    }
}