Rigorous Mathematical Proof | No Lucky Guess/Intuition
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\n# Algorithm (with explaination on an example)\n\nAt any point, if the n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n# Algorithm (with explaination on an example)\n\nAt any point, if the next item in the array is greater than (sum of all previous elements plus 1), then add (sum of all previous elements plus 1)\nin the array.\n\nInitialization: sum of all previous elements starts at 0.\n\nFor example, in array [1,5,10], target = 20\n\nlet\'s call sum of all previous elements as prevSum:\nInitialization: prevSum = 0\n\nIs 1 > prevSum + 1 = 1 ? No, Good we dont do anything, just update prevSum to 1 and move ahead.\n\nIs 5 > prevSum + 1 = 2? Yes, Add (prevSum + 1) = 2 to the array (array: [1, 2, 5, 10]) update prevSum to prevSum + new_element = (1 + 2 ) = 3 and move ahead. \n\n(Note: next time we again check 5, as we have to check the 3rd element next time which is again 5 after adding 2 in last step.)\n\nIs 5 > prevSum + 1 = 4? Yes, Add (prevSum + 1) = 4 to the array (array: [1, 2, 4, 5, 10]) update prevSum to prevSum + new_element = (3 + 4) = 7 and move ahead.\n\nIs 5 > prevSum + 1 = 8? No, Good we dont do anything, just update prevSum to (prevSum + 5) = 12 and move ahead.\n\nIs 10 >  prevSum + 1 = 13? No, Good we dont do anything, just update prevSum to (prevSum + 10) = 22 and move ahead.\n\nAs we already see th target of 20 is achieved, so let\'s stop. We have added two elements to the list so the answer is 2.\n\n# Proof\n\n**Definition:** Let A be an array [x1, x2, x3, . . . , x_r]. Then Span(A)\nis defined as a positive natural number x if all positive natural numbers less than or equal to x can be formed using elements in A and (x + 1) can not be formed using it.\n\nExample: Span([1,2,5]) = 3 as all of 1, 2 and 3 (3 = 1 + 2) can be formed using [1,2,5] but not 4. In other is words, 4 is the smallest positive natural number that can not be formed using [1,2,5] so 3 is the span of [1,2,5].\n\n**Lemma:** Let\'s suppose the first r elements in an array is A_r = [x1, x2, . . . , x_r] and Span(A_r) = x = x1 + x2 + . . . + x_r, then the span of A_(r+1) = [x1, x2, . . . , x_r, x_(r+1)] is x1 + x2 + . . . + x_r + x_(r+1) if and only if x_(r+1) <= x + 1 i.e x1 + x2 + . . . + x_(r+1).\n\nProof: The proof is trivial:\n\nAs we have to prove (A <=> B)\nProving First: \nB => A (i.e if x_(r+1) <= x + 1) => Span(A_(r+1)) = x1 + x2 + . . + x_(r+1)\n\n    Easier Part: No number bigger than x1 + x2 + . . . + x_r + x_(r+1)     can be formed using [x1, x2, . . . , x_r, x_(r+1)].\n\n    Other Part: Let y <=  x1 + x2 + . . . + x_r + x_(r+1) = x + x_(r+1). . . (1)\n\n    Claim: y can be formed. How? \n\n        if y <= x, it can be formed using first r elements itself as Span(A_r) = x = x1 + x2 + . . . + x_r.\n\n        else: x < y <= x + x_(r + 1) \n            therefore, y = x_(r+1) + z,\n            now z <= x ... from(1)\n            also z >= 0 (as z = y - x_(r+1) and y >= (x+1) and x_(r+1) <= x+1 (from 1))\n            Thus, z can be formed using first r elements, Thus y can be formed, so done.\n\nProving Other Way:\nA => B (i.e Span(A_(r+1)) = x1 + x2 + . . + x_(r+1) => i.e if x_(r+1) <= x + 1))\n\nNow, as we know that A => B is same as proving Not B => Not A:\n\nSo, we prove that if x_(r+1) > x + 1 => Span(A_(r+1)) != x1 + x2 + . . + x_(r+1) = x + x_(r+1).\n\nThis is pretty simple part: If x_(r+1) > x + 1. \nWe can\'t even form x + 1, as fisrt r items can only form upto x, and the next element is greater than (x + 1). So the span would be x itself as we can form all numbers till x and can not form (x + 1). Thus Span(A_(r+1)) can\'t be x + x_(r+1).\n\n                                                            Hence Proved \n\n\n**Theorem** Let\'s suppose the first r elements in an array is A_r = [x1, x2, . . . , x_r] and Span(A_r) = x = x1 + x2 + . . . + x_r, and the next element is greater than x + 1. Then there exist an optimal solution (one with minimum number of additions into the array) which would add (x + 1) to the array.\n\nProof: As Span(A_r) is sum of all previous elemnts ie (x = x1 + x2 + . . . + x_r), and next element in the array is greater than (x + 1), so we need to add a number to the array to form the element x + 1. \n\nThere are multiple possibilities which when added can make the sum x + 1. In particular, anything from [1, 2, 3,  . . . , x + 1] when added to existing array would do. As A_r can form (x + 1)- k for positive k, so adding extra k would do.\n\nWhich is the best choice, though? Ans: (x + 1), why?\n\nJustification: If i show that the Span([x1, x2, . . . , x_r, k]) is smaller than Span([x1, x2, . . . , x_r, x + 1]) for k < x + 1. Then, this would do, **why**?\n\n\n**{Jutification of Why, you can choose to read it later:** Lets say the optimal solution has array [x1, x2, . . . , x_r, k, y1, y2, .., y_t]\n\nThen [x1, x2, . . . , x_r, x+1, y1, y2, .., y_t] is also an optimal solution. \n\nBeacuse: is z is formed using [x1, x2, . . . , x_r, k, y1, y2, .., y_t], \nz = (elements from [x1, x2, . . . , x_r, k]) + elements from([y1, y2, .., y_t])\n\nNow, given that i show Span([x1, x2, . . . , x_r, k]) <= Span([x1, x2, . . . , x_r, x + 1]), thus the first part can be formed by Span([x1, x2, . . . , x_r, x + 1]) too. Thus z can be formed by [x1, x2, . . . , x_r, x + 1, y1, y2, .., y_t] too. Similarly, if you replace all added elements in the optimal solution by the one produced by this algorithm, you are bind to get an optimal solution.**}**\n\nComing back to the showing:\n\nSpan([x1, x2, . . . , x_r, k]) < Span([x1, x2, . . . , x_r, x + 1]) when \nk < x + 1.\n\nFrom if part of lemma: Span([x1, x2, . . . , x_r, k]) = x1 + x2 + . . . + x_r + k < x1 + x2 + . . . + x_r + (x + 1) = Span([x1, x2, . . . , x_r, x + 1]).\n\n                                                            QED\n\n\n\nNow, how does these lemma and theorem helps solve this problem?\n\nIf the first element of the sorted array is not 1, what choice do we have. Nothing rather than adding 1, as we also want to produce 1 and that can not be done using any other number.\n\nNow, lets say we have added 1 as our first element. Does the condition of theorem satisfies which is the span of first r element is sum fo first r element. Yes. As Span([1]) = 1 = sum of first 1 element. From, here ownwards the theorem suggests that, add an element (previous sum of all elements + 1) when next element is greater than (previous sum of all elements + 1) else dont. \n\n\n\n**Hi Guys, it took a lot of time and effort to devise and write the algorithm and its rigorous proof, upvote if it has helped you a bit. Also, feel free to ask questions if you have any, I will reply to them.**\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def minPatches(self, nums, n):\n        """\n        :type nums: List[int]\n        :type n: int\n        :rtype: int\n        """\n        \n        l = len(nums)\n        d = defaultdict(lambda : float("inf"))\n        for i in range(l):\n            d[i] = nums[i]\n\n        ans = 0 \n        baseSum = 0\n\n        i = 0\n        while True:\n            if baseSum >= n:\n                return ans \n\n            elif d[i] > baseSum + 1:\n                ans += 1\n                baseSum += baseSum + 1\n\n            else:\n                baseSum += d[i]\n                i+=1\n\n```
['Python']