0ms recursive solution in c++ (8 line code)


  • 9
    Y

    The idea is check number of 1 for each 10,100,1000,10000 ... position. For example, for 312:

    check 000~099, 100~199, 200~299, 300~312 and sum them up, for 000~099 and 200~299, it's countDigitOne(99), for 100~199 it's 100+countDigitOne(99), and for 300~312 it's countDigitOne(12).

    int countDigitOne(int n, int x){
        if(n == 0) return 0;
        if(n<10 || x==1) return 1;
        if(n/x == 1) return n-n/x*x+1+countDigitOne(n-n/x*x)+countDigitOne(x-1);
        return x+n/x*countDigitOne(x-1)+countDigitOne(n-n/x*x);
    }
    
    int countDigitOne(int n) {
        if(n <= 0) return 0;
        int x = 1, y=n;
        for(;y>=10;x*=10,y/=10);
        return countDigitOne(n, x);
    }

  • 0
    N

    why 100~199 is 100+countDigitOne(99)? not 100? 100~199 is 100 numbers,and they all contain digit one.


  • 0
    Y

    This problem asks for total number of 1 in all positive int below n, rather than number of positive int below n which contains 1. 100~199 contains 100 digit 1 at hundred position. We also need to count number of digit 1 at 10's position and 1's position. So we need to add countDigitOne(99)


  • 0
    A

    Inspired by yours idea

    def countDigitOne(self, n):
        if n < 0:
            return 0
        i = 1
        j = n
        while j >= 10:
            i *= 10
            j /= 10
        return self.count(n, i)
            
    def count(self, n, x):
        if n == 0 and x == 1:
            return 0
        elif n < 10 and x == 1:
            return 1
        elif n/x == 1:
            return self.countDigitOne(x-1) + (1+n%x) + self.countDigitOne(n%x)
        else:
            return x + (n/x)*self.countDigitOne(x-1) + self.countDigitOne(n%x)

Log in to reply
 

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