详细解释/Detailed Explanation with Example
\u4F8B\u5B50\uFF08Example\uFF09\n\n[1,2,3,5,10,50,70], n=100\n1. Seeing 1, we know [1,1] can be covered\n2. Seeing 2, we know [1,3] can be covered\n3. Similarly
**\u4F8B\u5B50\uFF08Example\uFF09**\n\n[1,2,3,5,10,50,70], n=100\n1. Seeing 1, we know [1,1] can be covered\n2. Seeing 2, we know [1,3] can be covered\n3. Similarly for 3, [1,6] can be covered\n4. for 5, [1,11] can be covered\n5. for 10, [1, 21] can be covered\n6. for 50, however, we have to add a patch, if the patch is 1, the range can be extended to [1, 22], if the patch is 2, the range can be extended to [1, 23]...From the observation we know in order to extend the range as longer as possible, we need to add 22, so that we get [1,43]. Why not add 23? Because [1,2,3,5,10,23] can NOT cover 22!\n6. [1,43] does not cover 50 yet. Following a similar way of thinking, we know this time we need to add 44, extending the range to [1, 87]\n7. for 70, it\'s already in [1,87], add 70 would extend the range to [1,157]\n8. 157 > 100, done\n\nIn conclusion, we need 2 patches, i.e., 22 and 44.\nSo the key point is if the current range is [1,m], and the current number > m, we need to add m+1 as a patch, to extend the range to [1, 2m+1].\n\n--------\n\n[1,2,3,5,10,50,70], n=100\n1. \u770B\u5230\u7B2C\u4E00\u4E2A\u65701\uFF0C\u6211\u4EEC\u77E5\u9053[1,1]\u53EF\u4EE5\u88AB\u8986\u76D6\n2. \u770B\u5230\u7B2C\u4E8C\u4E2A\u65702\uFF0C\u6211\u4EEC\u77E5\u9053[1,3]\u53EF\u4EE5\u88AB\u8986\u76D6\n3. 3\u540C\u7406\uFF0C[1,6]\u53EF\u4EE5\u88AB\u8986\u76D6\n4. 5\u540C\u7406\uFF0C[1,11]\u53EF\u4EE5\u88AB\u8986\u76D6\n5. 10\u540C\u7406\uFF0C[1,21]\u53EF\u4EE5\u88AB\u8986\u76D6\n6. \u73B0\u5728\u523050\uFF0C\u53D1\u73B0\u4E0D\u5F97\u4E0D\u6253\u8865\u4E01\u4E86\uFF0C\u5982\u679C\u6253\u8865\u4E011\uFF0C\u53EF\u4EE5\u6269\u5C55\u4E3A[1,22]\uFF0C\u5982\u679C\u6253\u8865\u4E012\uFF0C\u53EF\u4EE5\u6269\u5C55\u4E3A[1,23]...\u53EF\u89C1\uFF0C\u8981\u5F97\u5230\u6700\u5927\u7684\u8303\u56F4\uFF0C\u5E94\u8BE5\u6253\u7684\u8865\u4E01\u662F22\uFF0C\u8FD9\u6837\u80FD\u5F97\u5230[1,43]\uFF0C\u4E3A\u4EC0\u4E48\u4E0D\u80FD\u6253\u8865\u4E0123\u5462\uFF1F\u56E0\u4E3A[1,2,3,5,10,23]\u5F97\u4E0D\u523022\uFF01 \n7. [1,43]\u8FD8\u662F\u6CA1\u6709\u8986\u76D650\uFF0C\u6309\u7167\u7C7B\u4F3C\u7684\u903B\u8F91\uFF0C\u8FD9\u6B21\u5E94\u8BE5\u6253\u7684\u8865\u4E01\u662F44\uFF0C\u5C06\u8303\u56F4\u6269\u5145\u5230[1,87]\n8. \u6700\u540E\u523070\uFF0C\u5728[1,87]\u5185\uFF0C\u8303\u56F4\u88AB\u6269\u5145\u5230[1,157]\n9. 157 > 100\uFF0C\u7ED3\u675F\n\n\u7EFC\u4E0A\uFF0C\u4E00\u5171\u89812\u4E2A\u8865\u4E01\uFF0C\u537322\u548C44\n\u6240\u4EE5\uFF0C\u9898\u76EE\u7684\u8981\u70B9\u5728\u4E8E\uFF0C\u5982\u679C\u5F53\u524D\u7684\u8303\u56F4\u662F[1,m]\uFF0C\u4E14\u5F53\u524D\u7684\u6570\u5B57num > m\uFF0C\u6211\u4EEC\u5E94\u8BE5\u6253\u8865\u4E01m+1\uFF0C\u4F7F\u5F97\u8303\u56F4\u6269\u5145\u5230[1\uFF0C2m+1]\u3002\n\n\n**\u4EE3\u7801\uFF08Code\uFF09**\n```\ndef minPatches(self, nums: List[int], n: int) -> int:\n\tcnt = 0\n\tpatch = 0\n\ttot = len(nums)\n\ti = 0\n\twhile patch < n:\n\t\tif i < tot and patch + 1 >= nums[i]:\n\t\t\tpatch += nums[i]\n\t\t\ti += 1\n\t\telse:\n\t\t\tcnt += 1\n\t\t\t#print(patch+1)\n\t\t\tpatch += patch + 1  # patch + 1 is the new patch to be added\n\treturn cnt\n```
[]