# Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1
# repeated digit.
#
#
#
# Example 1:
#
# Input: 20
# Output: 1
# Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
# Example 2:
#
# Input: 100
# Output: 10
# Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99,
# and 100.
# Example 3:
#
# Input: 1000
# Output: 262
#
#
# Note:
#
# 1 <= N <= 10^9


# time complexity: O(log10(N))
class Solution(object):
    def numDupDigitsAtMostN(self, N):
        """
        :type N: int
        :rtype: int
        """

        # p(9,0) = 1
        # p(9,1) = p(9,0) * (9-1+1) = 9 * p(0) = 9
        # p(9,2) = p(9,1) * (9-2+1) = 8 * p(9,1) = 9 * 2
        # p(m,n) - given m elements, pick n elements from them,and there is no duplicate elements, how many ways to
        # do it

        # time : O(1)
        def permutation(m, n):
            if n == 0:
                return 1
            # assume m digits, you already choose n-1 digits, you can only choose m-(n-1) left elemetns to avoid
            # duplication
            return permutation(m, n - 1) * (m - n + 1)

        # notice we need to calculate [0, N+1), we need to take N itself into considertion
        # also, the code ` for j in xrange(0 if k else 1, v):`, assume the last num is 8,
        # it would only loop [0,7], so we need to +1
        digits, NN = [], N + 1

        # time : O(log10(N)), the digits # of N
        while NN:
            digits.insert(0, NN % 10)
            NN /= 10

        L, res = len(digits), 0

        # the main idea is calculate nums which has no repeated digits at all, then N - no-repeated = repeated

        # assume we have 2 cases
        # case 1 N = 7895, case 2 N = 7885
        # we could simply calculate
        # 1. x, xx, xxx
        # 2. 1xxx - 6xxx ( pick the prefix)
        # 3. 70xx - 77xx ( pick the prefix)
        # 4. 780x - 7879 (case 1), 78xx - 7879(case 2), since 7880 is already has duplicate, no need count any more
        # for case 2, the count would be terminated, because prefix 788 for case 2 is already has duplicate
        # 5. 7890-7895
        for i in xrange(1, L):
            # x , we have 9 * p(9,0) = 9, means we can choose 1-9
            # xx, we have 9 * p(9,1) = 9 * 9 * p(9,0) = 9 * 9, because x -> (1-9), second x has 9 choices because we
            # could choose 0
            # xxx , we have 9 * p(9,2) = 9 * 8 * p(9,1) = 9 * 9 * 8, etc
            res += 9 * permutation(9, i - 1)

        seen = set()
        # time: O(log10(N) * M) M : 1-9, so still O(log10(N))
        for k, v in enumerate(digits):
            # when k = 0, j can only start from 1 - 9
            for j in xrange(0 if k else 1, v):
                # j should not be picked before, otherwise, there is duplicate
                if j not in seen:
                    # for 1xxx - 6xxx, the first 'x', you have 9 choices, the second 'x' you have 8 choices, the third
                    # 'x' you have 7 choices. so it is 9 * 8 * 7 = p(9,3), j loops from 1 -> 9, so total is 9 * p(9,3)

                    # for 70xx-77xx, you have p(8,2) = 8 * 7, because we have 2 digits fixed, so only 10-2=8 digit left
                    # for us to choose, among them, we need to pick 2 digit to replace 'xx',
                    # j = 0->7, but 7 is already chosen, we have only 7 * p(8,2)

                    # when it comes case 1 7895 :  780x - 788x,notice 8 is already duplicate, but 7,8 is already in seen
                    # so we are able to skip it, we have 3 num fixed, so we have 10-3 = 7 choices, from them ,
                    # we need to
                    # pick 1 num, so we got p(7,1). j : 0->8, both 7, 8 not able to pick, we have p(7,1), j : 0->8
                    # but 7,8 is not available, so 7 * p(7,1)

                    # then for 7890 - 7895, j: 0->6 (remember N+1), so we have 6 * p(7,1) = 6
                    res += permutation(9 - k, L - k - 1)

            # for case 7885, when k = 2, v = 8, but v is already in seen, means we already duplicated, no need to continue
            if v in seen:
                break
            seen.add(v)

        return N - res


if __name__ == '__main__':
    print Solution().numDupDigitsAtMostN(20)
    print Solution().numDupDigitsAtMostN(30)
    print Solution().numDupDigitsAtMostN(34)
    print Solution().numDupDigitsAtMostN(100)
    print Solution().numDupDigitsAtMostN(1000)
