My 0ms C++ solution that is very easy to understand


  • 0
    J

    int countDigitOne1(int n) // Score 0ms
    {
    long ct = 0;
    if (n >= 1)
    {
    long i = 1;
    long j = 2i - 1;
    long divisor = 10
    i; // Initial divisor
    long q = n/divisor; // quotient
    long r = n%divisor; // reminder

    	while (q > 0)
    	{
    		// Count number of 1 in i(s)' digit
    		ct += q*i;
    		// Check whether r is in [0, i), [i, j), or [j, 10*i-1]
    		if (j <= r) // Complete package
    			ct += i;
    		if ((i <= r) & (r < j)) // Partial package
    			ct += r + 1 - i; // i - (2*i-1 - r);
    		// Note that when r < i, there is no package
    
    		// Update parameters
    		i *= 10; j = 2*i -1;
    		divisor = 10*i;
    		q = n/divisor;
    		r = n%divisor;
    	}
    	// The corner case that q = 0
    	if (j <= r) // Complete package
    		ct += i;
    	if ((i <= r) & (r < j)) // Partial package
    		ct += r + 1 - i; // j - (2*i-1 - r);
    	// Note that when r < i, there is no package
    }
    
    return ((int)ct);
    

    }


  • 0
    J

    class Solution {
    public:
    int countDigitOne(int n)
    {
    long ct = 0;
    if (n >= 1)
    {
    long i = 1;
    long j = 2i - 1;
    long divisor = 10
    i; // Initial divisor
    long q = n/divisor; // quotient
    long r = n%divisor; // reminder

    		while (q > 0)
    		{
    			// Count number of 1 in i-th digit
    			ct += q*i;
    			// Check whether r is in [0, i), [i, j), or [j, 10*i-1]
    			if (j <= r) // Complete package
    				ct += i;
    			if ((i <= r) & (r < j)) // Partial package
    				ct += r + 1 - i; // i - (2*i-1 - r);
    			// Note that when r < i, there is no package
    
    			// Update parameters
    			i *= 10; j = 2*i -1;
    			divisor = 10*i;
    			q = n/divisor;
    			r = n%divisor;
    		}
    		// The corner case that q = 0
    		if (j <= r) // Complete package
    			ct += i;
    		if ((i <= r) & (r < j)) // Partial package
    			ct += r + 1 - i; // j - (2*i-1 - r);
    		// Note that when r < i, there is no package
    	}
    
    	return ((int)ct);
    }
    

    };


Log in to reply
 

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