0ms recursion


  • 0
    B

    class Solution {
    public:

    int countDigitOne(int n) {
        int sum = 0;
        return recursiveCount(n,sum);
    }
    int recursiveCount(int n,int &sum){
        if (n <= 0) return sum;
        if (n < 10) return sum+1;
        
        if (n > 0){
            int nCounter = 0;
            long m = 1;
            
            while (n >= 10*m){
                nCounter++;
                m = m*10;
            }
            
            int multiplier = n/m;
            
    
            sum += multiplier*(nCounter*pow(10,nCounter-1)) + min(pow(10,nCounter)*1.0,n - pow(10,nCounter)+1);
    
            return recursiveCount(n-multiplier*pow(10,nCounter),sum);
        }
        return sum+1;
    }
    

    };


Log in to reply
 

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