Java/Python one pass solution easy to understand


  • 93

    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


Log in to reply
 

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