Massive Algorithms: LeetCode 233 - Number of Digit One

LeetCode 233 - Number of Digit One

[LeetCode] Number of Digit One 数字1的个数 - Grandyang - 博客园
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
Hint:

Beware of overflow.

X. Digit DP

https://www.cnblogs.com/yrbbest/p/5002299.html

-- Add cache

    public int countDigitOne(int n) {
        if (n < 1)
            return 0;
        if (n < 10)
            return 1;
        int baseInTen = (int)Math.pow(10, String.valueOf(n).length() - 1);   
        int highestDigit = n / baseInTen;         // get the highest digit of n
        
        if(highestDigit == 1)
            return countDigitOne(baseInTen - 1) + (n - baseInTen + 1) + countDigitOne(n % baseInTen);
        else
            return highestDigit * countDigitOne(baseInTen - 1) + baseInTen + countDigitOne(n % baseInTen);
    }

https://leetcode.com/problems/number-of-digit-one/discuss/64383/My-simple-and-understandable-Java-solution

public static int countDigitOne(int k) {
    int count = 0, factor = 1, n = k;
    while(n>0){
     int m = n/10, r = n%10, amount;
     
     if(r == 0) amount = 0;
     else if(r > 1) amount = factor;
     else amount = k%factor+1;
 
     count += m*factor + amount;
     factor *= 10;
     n = n/10;
    }
    return count;
}

https://blog.csdn.net/Guo15331092/article/details/78177059

先从DP开始说起。Dynamic Programming 我的简单理解是，将原问题分解为相同性质的子问题 (这一步分解很重要！). 然后需要的就是推导出子问题与原问题之间的联系（如果把不同规模的问题，看作是相同问题的不同状态，这这个联系的函数表达即是常说的状态转移方程）

数位DP其实就是DP的一种形式罢了。有区别与一般的DP在于，对于一般的数n,状态的转移一般是在同一个数量级上的转移。不负责任的写一个常用的一维DP形式：

f[k] = func(f[k - 1], f[k - 2], ... f[k - n])

这个式子里面， func函数是实现状态转移的主体，视不同情况而不同。需要注意的是这里func的参数是该问题的前n个状态。这与当前状态处于同一个数量级上。

而数位DP则显得更加“效率”，它的状态转移是从logNlogN转移上来的。比如说直接从f[10]转移到f[100]，再到f[1000]之类。这类DP的状态转移是在数位上进行的。换个角度去看，即是从状态2（2位）转移至状态3（3位），再到状态4.（4位）

f[k] = func(f[k - 1], f[k - 2], ... f[k - n])

这道题的数位DP形式是特别典型的那种。所以就先闲扯了一点。下面来看这题本身。由于这是裸数位DP，所以思路什么的就略去了。下面直接开始推最关键的，状态转移方程。

要推方程还得先看问题要怎么分解为子问题。来举个栗子：n = 2101.

如果稍微能类比一下的话，套用上面写的一维DP的形式，很容易猜想到可能方程会以如下形式出现：

f[2101] = func(f[1000], f[100], f[10], f[1])

这就是在数位上而言，的前几个状态嘛~

这里我们也可以看到，数位DP可以用非常少的状态来得到我们需要的下一个状态。这侧面反映了我们如果迭代去计算时必然包含了大量的重复运算。重复在哪里？以上面那个例子，来具体列举几个：

f[2000] = f[1000] + f[2000] - f[1000]

这样写的目的，就是把2000分成两部分去看。然后对应上，是不是发现，除了最高位，其他都是相等的1的个数呢。。。

001,002...100...998, 999

1001,1002...1100...1998, 1999

所以可以看到，我们只要算出了f[1000], 事实上f[2000]是可以直接推出的，有f[2000] = 2 * f[1000] + 1000

在这里我要特别说明一下，这里的f[1000]是不包含1000本身的，计算的是从1~999中1的个数。这样做的目的就是为了使状态转移方程好看一些。

类似的，我们应该能够推出，f[2101] = 2 * f[1000] + 1000 + f[100] + f[1]

推到这一步，我们做到什么程度了呢？就是把任意一个数n的f[n]分解为了几个 10n10n 的状态。（再提醒一句，在数位DP中，这些就是连续状态）换个表述来说，我们可以把原问题的任意状态，表示为一系列“基状态”的线性组合（对于一般的DP，这里应该写组合，而这题而言，显然是线性的）。下面需要推导的，就是基状态之间如何转移的。

实际上呢。。。基状态的转移和上面的，把原问题分为一系列基状态的过程，十分类似。考虑f[10]->f[100]:

f[100] = f[100] - f[90] + f[90] - f[80]...- f[10] + f[10]

拆分出来的10个部分，每一部分的值与f[10]都有紧密联系。除了10~19这一部分，其他的9部分值是和f[10]相同的。

讲了这么多，我觉得大概直接贴状态转移应该也能懂了吧。。

f[i] => 1 ~ (10 ^ i - 1) 中 1 的出现次数

f[i] = 10 * f[i - 1] + num(i - 1), num(i - 1)为 pow(10, i - 1)

实际上当数位为1时，需要另外讨论。这在代码中也有体现。正是这一点，使得计算1的个数比其他数字来的稍微容易一点： 1的话只要讨论>1和=1的情况。其他数字要讨论3种（0除外）

int countDigitOne(int n) {

if (n < 1) return 0;

int i = 0, dealt = 0, ans = 0;

int f[20];

memset(f, 0, sizeof(f));

// f[i] => 1 ~ (10 ^ i - 1) 中 1 的出现次数

// f[i] = 10 * f[i - 1] + num(i - 1), num(i - 1)为 pow(10, i - 1)

// dealt: 已经处理完的数字（n的某个右侧部分）

while (n > 0) {

int t = n % 10;

n/= 10;

f[i] = i * pow(10, i - 1);

if (t == 1) ans+= dealt + 1 + f[i];

else if (t > 1) ans+= t * f[i] + pow(10, i);

dealt+= t * pow(10, i);

i++;

}

return ans;

}

https://leetcode.com/problems/number-of-digit-one/discuss/111528/Java-DP-Solution

private Integer[][][] dp = new Integer[32][32][2];
public int countDigitOne(int n) {
    if (n <= 0) return 0;
    if (n < 10) return 1;
    char[] ns = String.valueOf(n).toCharArray();
    return help(ns, 0, 0, 0);
}
private int help(char[] ns, int index, int temp, int less) {
    if (index == ns.length) return temp;
    if (dp[index][temp][less] != null) return dp[index][temp][less];
    int res = 0;
    if (less == 1) {
        // if preview digit is already less than n
        // current digit can be 0-9
        res = help(ns, index + 1, temp + 1, less) + 9 * help(ns, index + 1, temp, less);
    } else {
     // if previous digit is equal to n
        if (ns[index] == '0') {
            res = help(ns, index + 1, temp, less); // current digit must be 0
        } else if (ns[index] == '1') {
            res = help(ns, index + 1, temp, 1)  // current digit is 0
             + help(ns, index + 1, temp + 1, 0); // current digit is 1
        } else {
            res = help(ns, index + 1, temp + 1, 1)  // 1
             + help(ns, index + 1, temp, 0)   // equals
             + (ns[index] - '1') * help(ns, index + 1, temp, 1);  // other numbers
        }
    }
    dp[index][temp][less] = res;
    return res;
}

https://leetcode.com/problems/number-of-digit-one/solution/

Approach #2 Solve it mathematically [Accepted]

In Approach #1, we manually calculated the number of all the

&#x27;1&#x27;

s in the digits, but this is very slow. Hence, we need a way to find a pattern in the way

&#x27;1&#x27;

s (or for that matter any digit) appears in the numbers. We could then use the pattern to formulate the answer.

Consider the

1

s in

\text{ones}

place ,

\text{tens}

place,

\text{hundreds}

place and so on... An analysis has been performed in the following figure.

From the figure, we can see that from digit '1' at

\text{ones}

place repeat in group of 1 after interval of

10

. Similarly, '1' at

\text{tens}

place repeat in group of 10 after interval of

100

. This can be formulated as

(n/(i*10))*i

Also, notice that if the digit at

\text{tens}

place is

\text{&#x27;1&#x27;}

, then the number of terms with

\text{&#x27;1&#x27;s}

is increased by

x+1

, if the number is say

\text{&quot;ab1x&quot;}

. As if digits at

\text{tens}

place is greater than

1

, then all the

10

occurances of numbers with

&#x27;1&#x27;

\text{tens}

place have taken place, hence, we add

10

. This is formluated as

{\min(\max((\text{n mod (i*10)} )-i+1,0),i)}

Lets take an example, say

n= 1234

No of

\text{&#x27;1&#x27;}

\text{ones}

place =

1234/10

(corresponding to 1,11,21,...1221) +

\min(4,1)

(corresponding to 1231) =

124

No of

\text{&#x27;1&#x27;}

\text{tens}

place =

(1234/100)*10

(corresponding to 10,11,12,...,110,111,...1919) +

\min(21,10)

(corresponding to 1210,1211,...1219)=

130

No of

\text{&#x27;1&#x27;}

\text{hundreds}

place =

(1234/1000)*100

(corresponding to 100,101,12,...,199) +

\min(135,100)

(corresponding to 1100,1101...1199)=

200

No of

\text{&#x27;1&#x27;}

\text{thousands}

place =

(1234/10000)*10000

\min(235,1000)

(corresponding to 1000,1001,...1234)=

235

Therefore, Total =

124+130+200+235 = 689

Herein, one formula has been devised, but many other formulae can be devised for faster implementations, but the essence and complexity remains the same. The users are encouraged to try to divise their own version of solution using the mathematical concepts.

Algorithm

Iterate over $i$ from $1$ to $n$ incrementing by $10$ each time:
Add $(n/(i*10))*i$ to $\text{countr}$ representing the repetition of groups of $$i$ sizes after each $(i*10)$ interval.
Add ${\min(\max((\text{n mod (i*10)} )-i+1,0),i)}$ to $\text{countr}$ representing the additional digits dependant on the digit in $i$ th place as described in intuition.

Time complexity: $O(log_{10}(n))$ .
No of iterations equal to the number of digits in n which is $log_{10}(n)$

int countDigitOne(int n)

{

int countr = 0;

for (long long i = 1; i <= n; i *= 10) {

long long divider = i * 10;

countr += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);

}

return countr;

}

Approach #1 Brute force [Time Limit Exceeded]

Iterate over

i

from

1

n

Convert $i$ to string and count $\text{'1'}$ in each integer string
Add count of $\text{'1'}$ in each string to the sum, say $countr$

Time complexity: $O(n*log_{10}(n))$ .
- We iterate from $1$ to $n$
- In each iteration, we convert integer to string and count '1' in string which takes linear time in number of digits in $i$ , which is $log_{10}(n)$ .
Space complexity: $O(log_{10}(n))$ Extra space for the countr and the converted string $\text{str}$ .

int countDigitOne(int n) {

int countr = 0;

for (int i = 1; i <= n; i++) {

string str = to_string(i);

countr += count(str.begin(), str.end(), '1');

}

return countr;

}

1的个数含1的数字数字范围

1 1 [1, 9]

11 10 11 12 13 14 15 16 17 18 19 [10, 19]

1 21 [20, 29]

1 31 [30, 39]

1 41 [40, 49]

1 51 [50, 59]

1 61 [60, 69]

1 71 [70, 79]

1 81 [80, 89]

1 91 [90, 99]

11 100 101 102 103 104 105 106 107 108 109 [100, 109]

21 110 111 112 113 114 115 116 117 118 119 [110, 119]

11 120 121 122 123 124 125 126 127 128 129 [120, 129]

通过上面的列举我们可以发现，100以内的数字，除了10-19之间有11个‘1’之外，其余都只有1个。如果我们不考虑[10, 19]区间上那多出来的10个‘1’的话，那么我们在对任意一个两位数，十位数上的数字(加1)就代表1出现的个数，这时候我们再把多出的10个加上即可。比如56就有(5+1)+10=16个。如何知道是否要加上多出的10个呢，我们就要看十位上的数字是否大于等于2，是的话就要加上多余的10个'1'。那么我们就可以用(x+8)/10来判断一个数是否大于等于2。对于三位数也是一样，除了[110, 119]之间多出的10个数之外，其余的每10个数的区间都只有11个‘1’，那么还是可以用相同的方法来判断并累加1的个数

https://leetcode.com/discuss/64962/java-python-one-pass-solution-easy-to-understand

The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

if n = xyzdabc

and we are considering the occurrence of one on thousand, it should be:

(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1

iterate through all digits and sum them all will give the final answer

public int countDigitOne(int n) {

if (n <= 0) return 0;

int q = n, x = 1, ans = 0;

do {

int digit = q % 10;

q /= 10;

ans += q * x;

if (digit == 1) ans += n % x + 1;

if (digit > 1) ans += x;

x *= 10;

} while (q > 0);

return ans;

}

https://leetcode.com/discuss/58868/easy-understand-java-solution-with-detailed-explaination

Very Easy to Understand Java Solution 0ms. 附中文解释

解法I：预处理+从高位向低位枚举1的出现次数

预处理数组ones，ones[x]表示[0, 10 ^ x)范围内包含的1的个数

由高位向低位依次遍历数字n的每一位digit

记digit右边（低位）数字片段为n，size为当前位数，cnt为1的总数

若digit > 1，则cnt += digit * ones[size - 1] + 10 ^ size

若digit = 1，则cnt += n + ones[size - 1] + 1

int countDigitOne(int n) { long long int res(0); int highn(n), lowc(1), lown(0); while(highn > 0){ int curn = highn % 10; highn = highn / 10; if (1 == curn) { //higher: 0~(highn-1); lower: 0 ~ (lowc-1) res += highn * lowc; //higher: highn ~ highn; lower:0~lown res += lown + 1; } else if (0 == curn) { //curn < 1 //higher: 0~(highn-1); lower: 0 ~ (lowc-1) res += highn * lowc; } else { //curn > 1 res += (highn + 1) * lowc; } //update lown and lowc lown = curn * lowc + lown; lowc = lowc * 10; } return res; }
http://shaowei-su.github.io/2015/11/29/leetcode233/
预处理数组ones，ones[x]表示[0, 10 ^ x)范围内包含的1的个数由高位向低位依次遍历数字n的每一位digit 记digit右边（低位）数字片段为n，size为当前位数，cnt为1的总数若digit > 1，则cnt += digit * ones[size - 1] + 10 ^ size 若digit = 1，则cnt += n + ones[size - 1] + 1

Pattern: # of 1: < 1, # of 1 < 100, # of 1 < 1000...
cur = prev * 10 + 10 ** digits

    public int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        int ones = 0;
        for (long m = 1; m <= n; m *= 10) {
            long a = n / m;
            long b = n % m;
            ones += (a + 8) / 10 * m;
            if (a % 10 == 1) {
                ones += b + 1;
            }
        }
        return ones;
    }

    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return 0
        ones, x = [0], 0
        imax = (1 << 32) - 1
        while 10 ** x < imax:
            ones.append(ones[x] * 10 + 10 ** x)
            x += 1
        count, size = 0, len(str(n))
        for digit in str(n):
            digit = int(digit)
            size -= 1
            n -= digit * 10 ** size
            if digit == 1:
                count += ones[size] + 1 + n
            elif digit > 1:
                count += digit * ones[size] + 10 ** size
        return count

http://www.faceye.net/search/209814.html

intuitive: 每10个数, 有一个个位是1, 每100个数, 有10个十位是1, 每1000个数, 有100个百位是1. 做一个循环, 每次计算单个位上1得总个数(个位,十位, 百位).

例子:

以算百位上1为例子: 假设百位上是0, 1, 和 >=2 三种情况:

case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.

case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 + (92+1) 次.

case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141+1) *100 次.

以上三种情况可以用一个公式概括:

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

https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python

Go through the digit positions by using position multiplier m with values 1, 10, 100, 1000, etc.

For each position, split the decimal representation into two parts, for example split n=3141592 into a=31415 and b=92 when we're at m=100 for analyzing the hundreds-digit. And then we know that the hundreds-digit of n is 1 for prefixes "" to "3141", i.e., 3142 times. Each of those times is a streak, though. Because it's the hundreds-digit, each streak is 100 long. So (a / 10 + 1) * 100 times, the hundreds-digit is 1.

Consider the thousands-digit, i.e., when m=1000. Then a=3141 and b=592. The thousands-digit is 1 for prefixes "" to "314", so 315 times. And each time is a streak of 1000 numbers. However, since the thousands-digit is a 1, the very last streak isn't 1000 numbers but only 593 numbers, for the suffixes "000" to "592". So (a / 10 * 1000) + (b + 1) times, the thousands-digit is 1.

The case distincton between the current digit/position being 0, 1 and >=2 can easily be done in one expression. With (a + 8) / 10 you get the number of full streaks, and a % 10 == 1 tells you whether to add a partial streak.

Java version

public int countDigitOne(int n) {
    int ones = 0;
    for (long m = 1; m <= n; m *= 10)
        ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
    return ones;
}

https://leetcode.com/discuss/46366/ac-short-java-solution

http://blog.csdn.net/xudli/article/details/46798619

intuitive: 每10个数, 有一个个位是1, 每100个数, 有10个十位是1, 每1000个数, 有100个百位是1. 做一个循环, 每次计算单个位上1得总个数(个位,十位, 百位).

例子:

以算百位上1为例子: 假设百位上是0, 1, 和 >=2 三种情况:

case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.

case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 + (92+1) 次.

case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141+1) *100 次.

以上三种情况可以用一个公式概括:

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

[CODE]

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

http://www.cnblogs.com/grandyang/p/4629032.html

    int countDigitOne(int n) {
        int res = 0, a = 1, b = 1;
        while (n > 0) {
            res += (n + 8) / 10 * a + (n % 10 == 1) * b;
            b += n % 10 * a;
            a *= 10;
            n /= 10;
        }
        return res;
    }

http://codechen.blogspot.com/2015/07/leetcode-number-of-digit-one.html

    public int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        
        ArrayList<Integer> ones = new ArrayList<Integer>();
        ones.add(0, 0);
        for (int i = 0; Math.pow(10, i) < (double)Integer.MAX_VALUE; i++) {
            ones.add(i + 1, ones.get(i) * 10 + (int)Math.pow(10, i));
        }
        
        int result = 0;
        int k = n;
        for (int i = 0; k > 0; i++) {
            int digit = k % 10;
            if (digit == 1) {
                result += ones.get(i) + (n % ((int)Math.pow(10, i))) + 1;
            } else if (digit > 1) {
                result += digit * ones.get(i) + (int)Math.pow(10, i);
            }
            k = k / 10;
        }
        
        return result;
    }

X. Recursive
http://yuanhsh.iteye.com/blog/2227478

For example '8192':

1-999 -> countDigitOne(999)

1000-1999 -> 1000 of 1s + countDigitOne(999)

2000-2999 -> countDigitOne(999)

7000-7999 -> countDigitOne(999)

8000-8192 -> countDigitOne(192)

Count of 1s : countDigitOne(999)*8 + 1000 + countDigitOne(192)

Noticed that, if the target is '1192':

Count of 1s : countDigitOne(999)*1 + (1192 - 1000 + 1) + countDigitOne(192)

(1192 - 1000 + 1) is the 1s in thousands from 1000 to 1192.

public int countDigitOne(int n) {
if(n <= 0) return 0;
if(n < 10) return 1;
int base = (int)Math.pow(10, (n+"").length() - 1);
int k = n / base;
return countDigitOne(base - 1) * k +
(k == 1 ? (n-base+1) : base) +
countDigitOne(n % base);
}

https://leetcode.com/discuss/44496/5-lines-solution-using-recursion-with-explanation
var countDigitOne = function(n) {
if(n <= 0) return 0;
if(n < 10) return 1;
var base = Math.pow(10, n.toString().length - 1);
var answer = parseInt(n / base);
return countDigitOne(base - 1) * answer + (answer === 1 ? (n - base + 1) : base) + countDigitOne(n % base);
};

https://leetcode.com/discuss/65228/java-recursive-ac-solution
public int countDigitOne(int n) {
String numstr = Integer.toString(n);
return helper(n, numstr.length());
}
public int helper(int n, int len){
if(n < 1) return 0;
else if(len == 1) return 1;
int pow = (int)Math.pow(10, len-1);
int msd = n / pow;
if(msd == 0) return helper(n, len - 1);
return (msd == 1 ? n % pow + 1 : pow) + helper(n % pow, len - 1) + msd * helper(pow - 1, len - 1);
}

https://leetcode.com/articles/number-of-digit-one/
int countDigitOne(int n)
{
int countr = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
countr += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
}
return countr;
}

int countDigitOne(int n)
{
int countr = 0;
for (int i = 1; i <= n; i++) {
string str = to_string(i);
countr += count(str.begin(), str.end(), '1');
}
return countr;
}

Time complexity: $O(n*log_{10}(n))$ .
We iterate from $1$ to $n$
In each iteration, we convert integer to string and count '1' in string which takes linear time in number of digits in $i$ , which is $log_{10}(n)$ .

http://www.geeksforgeeks.org/count-numbers-0-digit/

// Returns 1 if x has 0, else 0

int has0(int x)

{

    // Traverse througn all digits of

    // x to check if it has 0.

    while (x)

{

        // If current digit is 0, return true

        if (x % 10 == 0)

          return 1;

        x /= 10;

}

    return 0;

}

// Returns count of numbers from 1 to n with 0 as digit

int getCount(int n)

{

    // Initialize count of numbers having 0 as digit

    int count = 0;

    // Travers through all numbers and for every number

    // check if it has 0.

    for (int i=1; i<=n; i++)

        count += has0(i);

    return count;

}

Read full article from [LeetCode] Number of Digit One 数字1的个数 - Grandyang - 博客园

LeetCode 233 - Number of Digit One

Labels

Popular Posts