組合數學 - 1的個數 1的個數

Mean: 

 輸入一個n，計算小于10^n的正整數中含有1的數的個數。

analyse:

這題是一道組合數學課後思考題。

基本思路：  組合數學乘法原則 + 容斥原理

n位數中，每位可選：{0,1,2,3,4,5,6,7,8,9},是以共有10^n種，其中要除掉每位都為0的情況，是以要減一。

其中每位上不選1的情況為：{0,2,3,4,5,6,7,8,9},是以共有9^n中，同樣要除掉全部為0的情況。

Time complexity：O(n)

Source code：