Share my c++ solution with O(lg n) time complexity


  • 1
    Q
    class Solution {
        public:
            int countDigitOne(int n) {
                if(n<=0) return 0;
                int curr=n, right=0, ans=0;
                while(curr>0){
                    if(curr%10>1){
                        ans+=(curr/10+1)*pow(10, right);
                    }
                    else if(curr%10==1){
                        ans+=(curr/10)*pow(10, right)+n%int(pow(10, right))+1;
                    }
                    else{
                        ans+=(curr/10)*pow(10, right);
                    }
                    curr/=10; right++;
                }
                return ans;
            }
        };

Log in to reply
 

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