I spent 4 hours on this shit I hate my life
Intuition\n Describe your first thoughts on how to solve this problem. \nIts basically just math, Im gonna die \n# Approach\n Describe your approach to solving 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIts basically just math, Im gonna die \n# Approach\n<!-- Describe your approach to solving the problem. -->\nlet n be a K digit integer\nWe will count the total number of non-duplicated integers\nWe split them up in 2 cases by counting <K digits and K digits\n\nFor < K digits\nI did abit of trial and error for this but the general form that you would get would be for each k number of digits\n$$9\\bullet\\sum^{K-3}_{i=0}\\Pi^9_{j=9-i}j + 9$$\n\nSo how i visualised it was for e.g. we wamt let K = 5 so we want to find all possible non-duplicated integers <10 000 i.e. [1,9 999]\n\nFrom 1000 to 9999 we have 10000 - 1000 = 9000 integers \nwe fix the 1st digit so we have 1XXX then for the 2nd digit we have 9 remaining unique digits so on and so forth. Resulting in 9x8x7 integers\nNow we permutate the first digit to be between 1 to 9\nHence from 1000 - 9999 we have 9x9x8x7 non-duplicated integers\n\nSimilarly, from 100 - 999 we have 9x9x8\nfrom 10 - 99 we have 9x9\nfrom 1 - 9 we have 9\n\nNow if we take the sum we get \n9x9x8x7 9x9x8 + 9x9 + 9\n\n\nFor a fixed length of K digits\nWe store each leading digit in seen\nThen we build the integer up by iterating from 0 (if not first digit) and 1(if first digit) up to the leading digit. If any of the digit was seen before then we skip it. We then permutate the remaining digits left. If the leading digit was already seen we can stop as we know it will no longer give us any non-duplicated integers.\n\nE.g. if we let n = 13579\nWe will calculate this in parts as well specifically from \n1XXXX - 1XXXX\n10XXX - 12XXX\n130XX - 134XX\n1350X - 1356X\n1357X - 13578\n(remember last number not inclusive, pretty sure you can tweak the code to include)\n\nAt the start we have 10 000, since the leading digit is the first digit and is 1 we skip it. We then store 1 inside seen. Now we have fixed the first digit.\n\nFor the second digit, we start building from 0 to 2 so we have 10XXX, 11XXX and 12XXX but since 11XXX is already a duplicate we will skip it. Giving us 2x8x7x6 non-duplicated integers. Now we fix the second digit to be 3\n\nFor the third digit we will consider 130XX, 131XX, 132XX, 133XX, 134XX, w can see that 131XX and 133XX already contains duplicates and hence we will skip them. Giving us 3x7x6. Then we fix the third digit to be 5\n\nSo on and so forth, resulting in a total of 2x8x7x6 + 3x7x6 + 4x6 + 5\n\nNow we take the sum \n9x9x8x7 9x9x8 + 9x9 + 9 + \n2x8x7x6 + 3x7x6 + 4x6 + 5 + 1 (to include n=13579) = 6102\nWe return 13579 - 6102 = 7477 which is the ans\n  \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nI believe it is $$O(log_{10}n)$$ as we are counting the number of digits\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nI think it is $$O(log_{10}n)$$ as well? as we only store the number of digits in both seen and numList\n# Code\n```\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        temp = n\n        numList = []\n        while temp > 0:\n            numList.insert(0, temp%10)\n            temp //=10\n        digits = len(numList)\n        totalNum = 0\n        res = 0\n        # less than K digits\n        for j in range(digits-1, 0, -1):\n            res = 9\n            for k in range(9, 9-j+1,-1):\n                res *= k\n            totalNum += res\n        #K digits\n        seen = {}\n        for i in range(0,digits):\n            leadingDigit = numList[i]\n            remainingDigits = len(numList) - i - 1\n            for j in range(1 if i==0 else 0, leadingDigit):\n                if j in seen:\n                    continue\n                res = 1\n                for k in range(9-i, 9-i-remainingDigits,-1):\n                    res *= k\n                totalNum += res\n            if leadingDigit in seen:\n                break\n            seen[leadingDigit] = 1\n        seen = {}\n        for num in numList:\n            if num in seen:\n                return n-totalNum\n            seen[num] = 1\n        return n-totalNum - 1\n```
['Python3']