Python O(logN) solution with clear explanation
The number of non-repeated digits can be easily calculated with permutaiton. We only need to exclude all the non-repeated digits to get the answer.\n\nLet\'s fi
The number of non-repeated digits can be easily calculated with permutaiton. We only need to exclude all the non-repeated digits to get the answer.\n\nLet\'s first consider about the cases where N=10^k\n**N=10**\nthe free digits are marked as `*`, so we only need to consider about `*` and `1*`\n* `*`: obviously all 1-digit numbers are non-repeated, so non-repeated number = 9\n* `1*`: we only need to consider about `1* <= 10`, so non-repeated number = 1\n\nThus, the result for N=10 is:\n`N - #non_repeat(*) - #non_repeat(1*) = 10 - 9 - 1 = 0`\n\n**N=100**\nthe free digits are marked as `*`, so we only need to consider about `*`, `**`, and `1**`\n* `*`: obviously all 1-digit numbers are non-repeated, so non-repeated number = 9\n* `**`: this can be calculated with permutation: leading digit has 9 options(1-9) and the last 1 digit has `10-1` options, thus the total permuation is `9 * permutation(9, 1)=81`. i.e: non-repeated number = 81\n* `1**`: we only need to consider about `1**<=100`, so non-repeated number =0\n\nThus, the result for N=100 is:\n`N - #non_repeat(*) - #non_repeat(**) - #non_repeat(1**) = 100 - 9 - 81 = 10`\n\n**N=1000**\n`#non_repeat(***) = 9 * permutation(9, 2) = 9 * 9 * 8 = 648`\nsimilarly, we can get:\n`N - #non_repeat(*) - #non_repeat(**) - #non_repeat(***) - #non_repeat(1***) = 1000 - 9 - 81 - 648 = 282`\n\nNow, let\'s consider a more general case:\n**N=12345**\nactually, we can get the count of non-repeated numbers  by counting all non-repeated numbers in following patterns:\n\n```\n    *\n   **\n  ***\n ****\n10***\n11*** (prefix repeated, skip)\n120**\n121** (prefix repeated, skip)\n122** (prefix repeated, skip)\n1230*\n1231* (prefix repeated, skip)\n1232* (prefix repeated, skip)\n1233* (prefix repeated, skip)\n12340\n12341 (prefix repeated, skip)\n12342\n12343\n12344 (prefix repeated, skip)\n12345\n```\n\nand use N to minus the count we will get the answer.\n\nReference implementation:\n```\n# given number n, see whether n has repeated number\ndef has_repeated(n):\n    str_n = str(n)\n    return len(set(str_n)) != len(str_n)\n\ndef permutation(n, k):\n    prod = 1\n    for i in range(k):\n        prod *= (n-i)\n    return prod\n\n# calculate number of non-repeated n-digit numbers\n# note: the n-digit number can\'t start with 0\n# i.e: n_digit_no_repeat(2) calculates the non-repeated\n#   numbers in range [10, 99] (inclusive)\ndef n_digit_no_repeat(n):\n    if n == 1:\n        return 9\n    else:\n        return  9 * permutation(9, n-1)\n\nclass Solution(object):\n    def numDupDigitsAtMostN(self, N):\n        """\n        :type N: int\n        :rtype: int\n        """        \n        N_str = str(N)\n        n_digit = len(N_str)\n        digits = map(int, N_str)\n        result = N - 1\n        prefix = 0\n        for i in range(1, n_digit):\n            result -= n_digit_no_repeat(i)\n        for i in range(n_digit):\n            # when we fix the most significant digit, it \n            # can\'t be zero\n            start = 0 if i else 1\n            for j in range(start, digits[i]):\n                if has_repeated(prefix * 10 + j):\n                    continue\n                if i != n_digit-1:\n                    result -= permutation(10-i-1, n_digit-1-i)\n                else:\n                    # optmized from `result -= has_repeated(prefix*10+j)`\n                    result -= 1\n            prefix = prefix*10 + digits[i]\n        return result + has_repeated(N)\n```
[]