Share my 0ms Java code


  • 2
    M
    public class Solution {
        public int countDigitOne(int n) {
            if (n <= 0) {
                return 0;
            }
            int count = 0;
            int copyN = n;
            for (int weight = 1; n > 0; weight *= 10) {
                int complete = n / 10;
                int lsb = n % 10;
                if (lsb < 1) {
                    count += weight * complete;
                } else if (lsb > 1) {
                    count += weight * (complete + 1);
                } else {  // lsb == 1
                    count += weight * complete + copyN % weight + 1;
                }
                n = complete;
            }
            return count;
        }
    }

  • 0
    T

    Your algorithm is amazing, but I can't figure it out. Could you give me some more detail?


  • 1
    M

    Thank you. I count the 1s digit by digit, which is the reason why weight | n is scaling up | down by a factor of 10. complete means how many "complete cycles" are there for the current digit. lsb means Least Significant Bit (my mistake here, should be lsd, that is, Least Significant Digit, not Bit).

    Example 1. 20, lsb = 0, complete = 20 / 10 = 2, which means we have (0)1, 11, there are 2 ones at the 10^0 digit.

    Example 2. 135, lsb = 5, complete = 135 / 10 = 13, which means not only we have (0)1, 11, 21, 31,..., 121, also we have 131, there are 14 ones at the 10^0 digit.

    Example 3. 131, lsb = 1, complete = 131 / 10 = 13, which means we have (0)1, 11, 21, 31,..., 121 and 131, a total of 14 ones at the 10^0 digit. It seems that this is identical with the previous case, however, n keeps scaling down by a factor of 10,which means we can only know the impact of higher-order (comparing to the current digit we are considering) digits, we do not know the impact of lower-order digits.

    Example 4. 115, currently, we consider the 10^1 digit, so weight = 10. n = 11, lsb = 1, complete = 11 / 10 = 1, which means we have (0)1. Considering this is 10^1 digit, each of them actually stands for 10, 11,..., 19, so we should add complete * weight = 1 * 10 = 10 to count. Although the input is 115, what we are dealing with now is 11, the information of lower-order digits is lost, that is the "5" in 115 is lost. copyN reminds us of the lost information. copyN % weight + 1 adds 110, 111,..., 115, a total of 6 ones at the 10^1 digit to count.


  • 0
    M

    see my answer below.


  • 0
    T

    Thank you so much. I have got it with your examples, which makes it easy for me.


  • 1
    T

    Are you Chinese? 你是中国人 吗?


  • 0
    M

    yes i am.......


  • 0
    T
    This post is deleted!

  • 0
    T

    You are't China now, right?


  • 0
    M

    nah. in california. just a mediocore software developer :p

    top developers usually don't come to leetcode.


Log in to reply
 

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