Detailed Explanation for Those Who Can't Understand (Took me 5 hours to figure out)


  • 5
    Y
    public class Solution {
        public int countDigitOne(int n) {
            if (n <= 0) return 0;
            int result = 0;
            // process each digit of n, compute the total number of 1's can appear on that digit, and sum the results
            // solution inspired by StefanPochmann, but I rewrote his one-liner into if statements to help myself understand
            for (long m=1; m<=n; m*=10) {
                // suppose we have abcxdef
                // consider we are at m = 1000 (position x), then a = abcx, b = def
                long a = n/m, b = n%m;
                // if x > 1, then each combination of 0~abc (total abc+1 ways) on abc and 0~999 (total = 1000) on def works => (abc+1)*1000
                if (a%10 > 1) {
                    result += (a/10+1) * m;
                }
                // if x == 1, then each combination of 0~(abc-1) (total abc ways) on abc and 0~999 (total = 1000) on def works => abc*1000
                // but when it comes to abc, since x == 1, we only have def+1 (including 0) ways the first three digits are abc, otherwise we will exceed the number n => def+1
                // total = abc*1000 + def+1
                if (a%10 == 1) {
                    result += (a/10)*m + b+1;
                }
                // if x == 0, this is the tricky part (IMO)
                // you can only have 0~(abc-1) (total abc ways) on abc and 0~999 (total = 1000) on def => abc*1000
                // this is because its still possible for x to be 1 on numbers less than abc0def
                // one example, assume i = c-1, then x can be 1 on the number abixdef
                // all the values from 0~abc-1 works, and thus we have abc*1000 ways.
                if (a%10 == 0) {
                    result += (a/10)*m;
                }
            }
            return result;
        }
    }
    
    

    Stephen used a smart (amazing) way to combine those if statements into a 1-liner:

    ones += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
    

    This is absolutely mind-blowing and took me 5 hours to figure out (maybe I'm not that smart so I have to work hard to make up on that). Basically, if a % 10 == 0, then a+8 will never produce a carry to the 10th digit, and hence (a+8)/10 = a/10. If a % 10 == 1, there is still no carry, but (a % 10 == 1) will get invoked and produce the correct result. If a % 10 > 1, then we will have a carry added to the 10th digit, it's the same as (a / 10 + 1).

    One liner solution by Steph here: https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python

    Code without comment (for cleaner view):

    public class Solution {
        public int countDigitOne(int n) {
            if (n <= 0) return 0;
            int result = 0;
            for (long m=1; m<=n; m*=10) {
                long a = n/m, b = n%m;
                if (a%10 > 1) {
                    result += (a/10+1) * m;
                }
                if (a%10 == 1) {
                    result += (a/10)*m + b+1;
                }
                if (a%10 == 0) {
                    result += (a/10)*m;
                }
            }
            return result;
        }
    }
    

  • 0
    L

    Thank you for the detailed explanation. I've learned a lot from it.

    Just a quick reminder that at the top you don't have to check the value of n cause the for loop won't run if n <= 1 and the result will be just 0.


Log in to reply
 

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