Share my O(logN) C++ DP solution with proof and explanation
---\n## 1. Problem\n\n---\nGiven a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.\n\nEx
---\n## 1. Problem\n\n---\nGiven a positive integer ```N```, return the number of positive integers less than or equal to ```N``` that have at least 1 repeated digit.\n\n**Example 1:**\n```\nInput: 20\nOutput: 1\nExplanation: The only positive number (<= 20) with at least 1 repeated digit is 11.\n```\n\n**Example 2:**\n```\nInput: 100\nOutput: 10\nExplanation: The positive numbers (<= 100) with at least 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.\n```\n\n**Example 3:**\n```\nInput: 1000\nOutput: 262\n```\n**Note:**\n* 1 <= N <= 10^9\n\n---\n## 2. Thinking process\n\n---\n#### 2.1 Analysis\n\n---\nThe problem is to return \n\n>#### T(N) = the number of positive integers less than or equal to N that have **at least 1 repeated digit**.\n\nSuppose\n\n>#### S(N) = the number of positive integers less than or equal to N that have **NO repeated digits**.\n\nThe answer can be expressed as\n\n>#### T(N) = N - S(N).\n\nLater, the calculation of S(N) will be focused on.\n\n---\n#### 2.2 Find the rules\n\n---\n\n- From **1** to **9**, there are **9** positive integers that have **NO repeated digits**.\n\n- From **10** to **99**,\n  - From **10** to **19**, there are **9** positive integers that have **NO repeated digits**. (Only **11** has repeated digits)\n  - From **20** to **29**, there are **9** positive integers that have **NO repeated digits**. (Only **22** has repeated digits)\n  - From **30** to **39**, there are **9** positive integers that have **NO repeated digits**. (Only **33** has repeated digits)\n  - From **40** to **49**, there are **9** positive integers that have **NO repeated digits**. (Only **44** has repeated digits)\n  - From **50** to **59**, there are **9** positive integers that have **NO repeated digits**. (Only **55** has repeated digits)\n  - From **60** to **69**, there are **9** positive integers that have **NO repeated digits**. (Only **66** has repeated digits)\n  - From **70** to **79**, there are **9** positive integers that have **NO repeated digits**. (Only **77** has repeated digits)\n  - From **80** to **89**, there are **9** positive integers that have **NO repeated digits**. (Only **88** has repeated digits)\n  - From **90** to **99**, there are **9** positive integers that have **NO repeated digits**. (Only **99** has repeated digits)\n  there are **9 \xD7 9 = 81** positive integers that have **NO repeated digits**.  \n  \n- From **100** to **999**,\n  - From **100** to **199**,\n    - From **100** to **109**, there are **8** positive integers that have **NO repeated digits**. (**100** and **101** have repeated digits)\n    - From **110** to **119**, there are **0** positive integers that have **NO repeated digits**. (**ALL numbers** have repeated digits because of the prefix **11**)\n    - From **120** to **129**, there are **8** positive integers that have **NO repeated digits**. (**121** and **122** have repeated digits)\n    - From **130** to **139**, there are **8** positive integers that have **NO repeated digits**. (**131** and **133** have repeated digits)\n    - From **140** to **149**, there are **8** positive integers that have **NO repeated digits**. (**141** and **144** have repeated digits)\n    - From **150** to **159**, there are **8** positive integers that have **NO repeated digits**. (**151** and **155** have repeated digits)\n    - From **160** to **169**, there are **8** positive integers that have **NO repeated digits**. (**161** and **166** have repeated digits)\n    - From **170** to **179**, there are **8** positive integers that have **NO repeated digits**. (**171** and **177** have repeated digits)\n    - From **180** to **189**, there are **8** positive integers that have **NO repeated digits**. (**181** and **188** have repeated digits)\n    - From **190** to **199**, there are **8** positive integers that have **NO repeated digits**. (**191** and **199** have repeated digits)\n    there are **9 \xD7 8 = 72** positive integers that have **NO repeated digits**.\n  - .....\n\nLet\'s think about all positive integers **from 100 to 199**.\n \nThey can be generated by \n\n>#### adding a new digit from **0** to **9** to the end of all positive integers from **10** to **19**.\nIn order to generate a new positive integer that has **NO** repeated digits,\n- To **10**: **10 has NO repeated digits**. There are **8 choices (0 and 1 can NOT be chosen)**.\n- To **11**: **11 has repeated digits**. There are **0 choices (0 to 9 can NOT be chosen)**.\n- To **12**: **12 has NO repeated digits**. There are **8 choices (1 and 2 can NOT be chosen)**.\n- To **13**: **13 has NO repeated digits**. There are **8 choices (1 and 3 can NOT be chosen)**.\n- To **14**: **14 has NO repeated digits**. There are  **8 choices (1 and 4 can NOT be chosen)**.\n- To **15**: **15 has NO repeated digits**. There are  **8 choices (1 and 5 can NOT be chosen)**.\n- To **16**: **16 has NO repeated digits**. There are  **8 choices (1 and 6 can NOT be chosen)**.\n- To **17**: **17 has NO repeated digits**. There are  **8 choices (1 and 7 can NOT be chosen)**.\n- To **18**: **18 has NO repeated digits**. There are  **8 choices (1 and 8 can NOT be chosen)**.\n- To **19**: **19 has NO repeated digits**. There are  **8 choices (1 and 9 can NOT be chosen)**.\n\nAre there rules?\n\n---\n>#### **Rule A:** \n>#### **A k-digit positive integer with NO repeated digits can ONLY be generated from (k - 1)-digit positive integers with NO repeated digits (k > 1).**\n\nProof:\n\nIf a (k - 1)-digit positive integer has repeated digits (e.g. **11**), \nafter adding a digit (**0** to **9**) to its end, the generated k-digit integer (e.g. 110, 111, ..., 119) **STILL has repeated digits**.\nThat\'s to say, a k-digit positive integer with **NO** repeated digits can **ONLY** be generated from (k - 1)-digit positive integers with **NO** repeated digits.\n\n---\n\n>#### **Rule B:** \n>#### **To generate a k-digit positive integer with NO repeated digits,** \n>#### **there are (10 - k + 1) digits that can be added to (k - 1)-digit positive integers with NO repeated digits (k > 1).**\n\nProof:\n\nA (k - 1)-digit positive integer **with NO repeated digits** has **k - 1 distinct digits**.\nWhen generating a k-digit positive integer **with NO repeated digits** from it, \nsince **k - 1** digits in **0** to **9** have been **used**, there are **10 - k + 1** choices for the digit to be added.\n\n\n---\n#### 2.3 Recursion formula\n\n---\nDefinition:\n\n>#### **f(i, j, k): The number of i-digit positive integers with NO repeated digits in the interval [j, k]. (i > 0, j \u2264 k, j and k are i-digit positive integers).**\n\n\nBased on the **Rule A and Rule B in Section 2.2**, the recursion formula is\n\n>#### **f(i, j, k) = k - j + 1. i = 1.**\n>#### **f(i + 1, 10j, 10k + 9) = f(i, j, k) \xD7 (10 - i). others.**\n\n---\n#### 2.4 Normal case analysis\n\n\n---\n\nIn order to illustrate the usage of the recursion formula in Section 2.3, we take a normal case for calculation.\n\nIf **N = 26334**,\n\nFrom **Section 2.3**,\n \n- From **1** to **9**, f(1, 1, 9) = 9.\n- From **10** to **99**, f(2, 10, 99) = f(1, 1, 9) \xD7 (10 - 1) = 9 \xD7 9 = 81.\n- From **100** to **999**, f(3, 100, 999) = f(2, 10, 99) \xD7 (10 - 2) = 81 \xD7 8 = 648.\n- From **1000** to **9999**, f(4, 1000, 9999) = f(3, 100, 999) \xD7 (10 - 3) = 648 \xD7 7 = 4536.\n\nIf all values are added together, the sum is\n\n>#### **S(9999) = f(1, 1, 9) + f(2, 10, 99) + f(3, 100, 999) + f(4, 1000, 9999) = 9 + 81 + 648 + 4536 = 5274.**\n\nNow the number of positive integers **with NO repeated digits less than or equal to 9999** has been calculated, which is the **first part of the whole result**.\n\n\n---\nHow about the rest?\n\nThe rest part is the number of positive integers **with NO repeated digits in interval [10000, 26334]**, which is\n\n>#### **P = f(5, 10000, 26334)**.\n\nHow can the recursion formula be applied here?\n\n---\nSince our target is to **calculate f(5, 10000, 26334)**, the **calculation series** is\n\n>#### **f(1, 1, 2), f(2, 10, 26), f(3, 100, 263), f(4, 1000, 2633), f(5, 10000, 26334).**\n\n\n- From **1** to **2**, **f(1, 1, 2) = 2**.\n\n\n- From **10** to **29**, by applying the recursion formula, **f(2, 10, 29) = f(1, 1, 2) \xD7 (10 - 1) = 2 \xD7 9 = 18**.\n\n  - From **27 to 29**, there are **3** positive integers **with NO repeated digits**, which means **f(2, 27, 29) = 3**.   \n\n  - **f(2, 10, 26) = f(2, 10, 29) - f(2, 27, 29) = 18 - 3 = 15**.\n  \n\n- From **100** to **269**, by applying the recursion formula, **f(3, 100, 269) = f(2, 10, 26) \xD7 (10 - 2) = 15 \xD7 8 = 120**.\n\n  - From **264 to 269**, there are **5** positive integers **with NO repeated digits** (**except 266**), which means **f(3, 264, 269) = 5**.\n  \n  - **f(3, 100, 263) = f(3, 100, 269) - f(3, 264, 269) = 120 - 5 = 115**.\n  \n  \n- From **1000** to **2639**, by applying the recursion formula, **f(4, 1000, 2639) = f(3, 100, 263) \xD7 (10 - 3) = 115 \xD7 7 = 805**.\n\n  - From **2634 to 2639**, there are **5** positive integers **with NO repeated digits** (**except 2636**), which means **f(4, 2634, 2639) = 5**.\n  \n  - **f(4, 1000, 2633) = f(4, 1000, 2639) - f(4, 2634, 2639) = 805 - 5 = 800**. \n\n  \n- From **10000** to **26339**, by applying the recursion formula, **f(4, 10000, 26339) = f(4, 1000, 2633) \xD7 (10 - 4) = 800 \xD7 6 = 4800**.\n\n  - From **26335 to 26339**, there are **NO** positive integers **with NO repeated digits** (**due to the prefix "2633"**), which means **f(5, 26335, 26339) = 0**.\n  \n  - **f(5, 10000, 26334) = f(4, 10000, 26339) - f(5, 26335, 26339) = 4800 - 0 = 4800**.\n\nThis is the **second part of the whole result**.\n\n---\nThen\n\n>#### **S(26334) = S(9999) + f(5, 10000, 26334) = 5274 + 4800 = 10074.**\n\n\nThe final answer is\n\n>#### **T(26334) = 26334 - S(26334) = 26334 - 10074 = 16260.**\n\n---\n#### 2.4 Algorithm\n\n\n---\n**Special case**:\n- If N < 10, return 0.\n\n---\n**Get digits**:\n- Initialization:\n\n  - Set k = 0. i = N.\n\n- Loop: while i > 0, \n  \n  - Set k = k + 1. (Now, k is the digit length of N).\n\n  - Set i = i / 10. \n  \n- Initialization: \n\n  - Set j = N.\n\n  - Array digit with size = k. (saving all digits in N)\n  \n- Loop: iterate i from 0 to k - 1\n\n  - Set digit[k - 1 - i] = j mod 10.\n  \n  - Set j = j / 10.\n\n---\n**Get first part**:\n\n- Initialization: \n\n  - Array noDupBase with size = k - 1. \n  \n  - Set noDupBaseSum = 0. (calculate first part)\n\n- Loop: iterate i from 0 to k - 2.\n\n  - If i = 0, noDupBase[i] = 9. Calculate f(1, 1, 9).\n  \n  - Else, noDupBase[i] = noDupBase[i - 1] \xD7 (10 - i). Calculate f(i, 10^(i - 1), 10^i - 1).\n  \n  - Set noDupBaseSum = noDupBaseSum + noDupBase[i].\n\n---\n**Get second part**:\n\n- Initialization: \n\n  - Set boolean value duplicate = false. (prefix duplicate) \n  \n  - Array count with size = 10.(record the digits\' count in prefix). \n  \n  - Array noDupRes with size = k. (calculate second part)\n  \n- Loop: iterate i from 0 to k - 1.\n\n  - If i = 0, noDupBase[i] = 9. Calculate f(1, 1, 9).\n  \n  - Else, noDupBase[i] = noDupBase[i - 1] \xD7 (10 - i).\n  \n  - If NOT duplicate\n  \n    - Set diff = 0.\n\t\n\t- Loop: iterate j from digit[i] + 1 to 9\n\t\n\t  - If count[j] = 0, Set diff = diff + 1.\n\t  \n\t- Set noDupRes[i] = noDupRes[i] - diff.\n\t\n\t- Set count[digit[i]] = count[digit[i]] + 1.\n\t\n\t- If count[digit[i]] > 1, Set duplicate = true.\n\n---\n**Get final answer**:\n\t\n- return N - (noDupBaseSum + noDupRes[k - 1]).\n\n\n---\n## 4. Complexity Analysis\n\n---\n\n#### 4.1 Time complexity\n\n---\n\n>#### The time complexity is **O(logN)**.\n\n---\n\n#### 4.2 Space complexity\n\n---\n\n>#### The space complexity is **O(logN)**.\n\n---\n## 5. Code\n\n---\n```\nclass Solution {\npublic:\n    int numDupDigitsAtMostN(int N) {\n        if(N < 10) return 0;\n        int k = 0;\n        for(int i = N; i > 0; i /= 10) k++;\n        int digit[k] = {0};\n        for(int i = 0, j = N; i < k; i++, j /= 10) digit[k - 1 - i] = j % 10;\n        \n        int noDupBaseSum = 0;\n        int noDupBase[k - 1] = {0};\n        for(int i = 0; i < k - 1; i++)\n        {\n            noDupBase[i] = i == 0 ? 9 : noDupBase[i - 1] * (10 - i);\n            noDupBaseSum += noDupBase[i];\n        }\n        \n        int count[10] = {0};\n        int noDupRes[k] = {0};\n        bool duplicate = false;\n        for(int i = 0; i < k; i++)\n        {\n            noDupRes[i] = i == 0 ? 9 : noDupRes[i - 1] * (10 - i);\n            if(!duplicate)\n            {\n                int diff = 0;\n                for(int j = digit[i] + 1; j < 10; j++) diff += count[j] == 0;\n                noDupRes[i] -= diff;\n                count[digit[i]]++;\n                if(count[digit[i]] > 1) duplicate = true;\n            }\n        }\n        return N - (noDupBaseSum + noDupRes[k - 1]);\n    }\n};
['Math', 'Dynamic Programming', 'Recursion', 'C++']