Java/Python one pass solution easy to understand


  • 96

    The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

    if n = xyzdabc
    

    and we are considering the occurrence of one on thousand, it should be:

    (1) xyz * 1000                     if d == 0
    (2) xyz * 1000 + abc + 1           if d == 1
    (3) xyz * 1000 + 1000              if d > 1
    

    iterate through all digits and sum them all will give the final answer

    Java

    public int countDigitOne(int n) {
    
        if (n <= 0) return 0;
        int q = n, x = 1, ans = 0;
        do {
            int digit = q % 10;
            q /= 10;
            ans += q * x;
            if (digit == 1) ans += n % x + 1;
            if (digit >  1) ans += x;
            x *= 10;
        } while (q > 0);
        return ans;
    
    }
    
    // 40 / 40 test cases passed.
    // Status: Accepted
    // Runtime: 0 ms
    

    Python

    def countDigitOne(self, n):
        if n <= 0:
            return 0
        q, x, ans = n, 1, 0
        while q > 0:
            digit = q % 10
            q /= 10
            ans += q * x
            if digit == 1:
                ans += n % x + 1
            elif digit > 1:
                ans += x
            x *= 10
        return ans
    
    # 40 / 40 test cases passed.
    # Status: Accepted
    # Runtime: 32 ms
    # 97.59%

  • 0
    A

    This solution is great!


  • 3
    P

    I would really appreciate if someone can explain how/why does this work.


  • 1
    R

    this solution is much easier to be understood! thank you!


  • 0
    L

    This explanation is clear, thanks!


  • 0
    O

    For me this is the best explanation and implementation


  • 0
    B

    Great, Thanks for your sharing.


  • 0

    Spent quite sometime trying to figure out why we should do a n/m + 8.......
    Yours is much easier to understand! Thanks!


  • 0
    T

    I don't understand the algorithm , can you please explain it ?
    Thank you


  • 3
    I

    For people who doesn't understand the author's explanations, just look at some examples:

    Let n = 4560000

    How many nums with "1" at the thousand's position?

    4551000 to 4551999 (1000)
    4541000 to 4541999 (1000)
    4531000 to 4531999 (1000)
    ...
    1000 to 1999 (1000)

    That's 456 * 1000

    What if n = 4561234?

    4561000-4561234 (1234+1)
    4551000 to 4551999 (1000)
    4541000 to 4541999 (1000)
    4531000 to 4531999 (1000)
    ...
    1000 to 1999 (1000)

    That's 456 * 1000 + 1234 + 1

    What if n = 4562345?
    4561000-4561999 (1000)
    4551000 to 4551999 (1000)
    4541000 to 4541999 (1000)
    4531000 to 4531999 (1000)
    ...
    1000 to 1999 (1000)

    That's 456*1000 + 1000

    Same for hundred's position.

    Let n = 4012

    How many nums with "1" at the hundred's position?

    3100-3999 (100)
    2100-2999 (100)
    1100-1999 (100)
    100 to 199 (100)
    That's 4 * 100

    Let n = 4111

    4100-4111 ( 11 + 1)
    3100-3999 (100)
    2100-2999 (100)
    1100-1999 (100)
    100 to 199 (100)
    That's 4 * 100 + 11 + 1

    Let n = 4211

    4100-4199 (100)
    3100-3999 (100)
    2100-2999 (100)
    1100-1999 (100)
    100 to 199 (100)
    That's 4 * 100 + 100

    Same for ten's digit

    Let n = 30
    How many nums with "1" at the ten's position?

    210-219 (10)
    110-119 (10)
    10-19 (10)

    That's 3 * 10

    Let n = 312

    310-312 (2 + 1)
    210-219 (10)
    110-119 (10)
    10-19 (10)
    That's 3 * 10 + 2 + 1

    Let n = 322

    310-319 (10)
    210-219 (10)
    110-119 (10)
    10-19 (10)
    That's 3 * 10 + 10

    Same for one's digit

    Let n = 30
    How many nums with "1" at the one's position?

    21 (1)
    11 (1)
    1(1)
    That's 3 * 1

    Let n = 31
    How many "1" are there at the one's position?
    31 (1)
    21 (1)
    11 (1)
    1 (1)
    That's 3 * 1 + 1

    Let n = 32
    How many "1" are there at the one's position?
    31 (10)
    21 (10)
    11 (10)
    1 (10)
    That's 3 * 1 + 1

    Let n = 3

    only 1 (10 of "1" at one's position)

    That's 0 * 1 + 1


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.