Python 3 line easy to understand recursive solution, with some comments


  • 0
    X
        def countDigitOne(self, n):
            if n < 10: return 1 if n >= 1 else 0
            h = int(pow(10, int(math.log10(n))))
            return (h if n/h >= 2 else n - h + 1) + (n/h)*self.countDigitOne(h - 1) + self.countDigitOne(n % h)
    

    Line 1: If n only contains 1 bit, return how many "1"s.
    Line 2: Get highest bit, e.g., if n is 265328, then h is 100000
    Line 3: (h if n/h >= 2 else n - h + 1) is how many "1" occurs at the most significant bit (using h to calculate); then, recursively call f(99999) and f(65328), f(99999) needs to *2 because the highest digit is 2.


Log in to reply
 

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