✏️ 100%Beats 💯 || 5 Language 🚀|| 🪩🫧Best visualization🎯|| Best formatted🍸🥂🫧✧˖°|
\uD83C\uDF89 Screenshot \uD83D\uDCF8\n\n\n\n\n## Input \uD83D\uDCE5 \n\n    One Sorted* Number Array (nums)  & (N) \n\n    1 <= nums[i] <= 10^4\n\n    1 <= N <=
# \uD83C\uDF89 Screenshot \uD83D\uDCF8\n\n![330.png](https://assets.leetcode.com/users/images/4da4528d-c664-414e-9728-55d2b25afc20_1718510944.069194.png)\n\n\n## Input \uD83D\uDCE5 \n\n    One Sorted* Number Array (nums)  & (N) \n\n    1 <= nums[i] <= 10^4\n\n    1 <= N <= 2^31 - 1\n\n\n## Output \uD83D\uDCE4\n\n    We have to count number of patches (added number) by which \n\n    our array subArray sum become in (Range[1, N]) \n\n    Means by adding any number we got sum 1 <= Sum <= N\n\n\n# Intuition \uD83E\uDD14\uD83D\uDCAD\n\n\n    We are given number array so we just have to count number of\n\n    patches so that sum of any number of our arr become 1 <= Sum <= N\n\n\n\n# Example \uD83D\uDCDC\n\n    `Ex.`\n\n        nums = [1, 3],  n = 6 \n\n        1. arr = [1]; reach = 1; pactes = 0 \n        \n             add 2 to our array\n\n        2. arr = [1, 2] maxNumReach = 3 (1 + 2) pactes = 1 \n\n             add 3 to our array\n        \n        3. arr = [1, 2, 3] maxNumReach = 6 (1 + 2 + 3) pactes = 1 \n\n\n\n# Approach \u270D\uD83C\uDFFC\n \n    we have to make our subarray sum to max untill we reach given N\n\n    By either adding our own elements or elemets giving in array \n\n    So if we add 1 number from given in array we can reach \n\n    upto perivous reach + adding that number \n\n    cause we had our maxSum of sub Array before so if \n\n    we are adding another element  It can reach upto \n\n        previous + current adding element \n\n    and if we don\'t add any number given in nums array \n\n    The max possible element we can add is ourself cause we have to \n\n    maximize our sum and catch is we\'ve to addd given array element \n\n    so once we exceed number present at Ith after adding ourself \n\n    to maximize we will add that number too just to minimize \n \n    The patches cause adding another ourself inc patche by one\n\n\n### I think you all got the idea so let\'s just go step by step\n\n\n# Step wise \uD83E\uDE9C\n\n\n        There will be 3 steps \n\n    Step 1 \u27A4 Take three var i = 0, reach = 1, patches = 0  \n\n            \u2022 we assign reach = 1 cause we have to go { 1 <= N }\n\n            \u2022 cause adding elem will be a very long number so we\'ll make \n\n            \u2022 our (Reach A Long Number)\n\n    Step 2 \u27A4 apply while loop until we get reach <= n \n\n            \u2022 To inc our reach we have two option \n\n            Option 1 \u27A4 add nums\'s number  \n\n                \u2022 If we exceed our reach by Ith number \n\n                    -> consider that we should have elem in nums\n\n                \u2022 We will add number to our reach\n\n            Option 2 \u27A4 add our self and inc patches by 1\n\n                \u2022 We just inc our reach by adding ourself\n\n    Step 3 \u27A4 return patches\n\n\n\n\n# Complexity \uD83C\uDFD7\uFE0F\n- \u231A Time complexity: $$O(n)$$ `n = given`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- \uD83E\uDDFA Space complexity: $$O(1)$$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code \uD83D\uDC68\uD83C\uDFFB\u200D\uD83D\uDCBB\n\n``` JAVA []\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        // REACH is number up to which we can add our number and got value\n        long reach = 1;\n        int i = 0;\n        int patches = 0;\n\n        // we have to go up to given n so we\'ll loop for reach until it reaches n\n        while (reach <= n) {\n            // if we exceed the value present in array\n            if (i < nums.length && nums[i] <= reach) {\n                // we\'ll add our array value\n                reach += nums[i++];\n            } else {\n                // else we\'ll keep adding ourself to reach (N)\n                reach += reach;\n                // If we add ourself mean we added a number to array hence we inc our patches\n                // count\n                patches++;\n            }\n        }\n\n        return patches;\n    }\n}\n``` \n``` C++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        // REACH is number up to which we can add our number and got value\n        long long reach = 1;\n        long long patches = 0;\n        long i = 0;\n\n        // we have to go up to given n so we\'ll loop for reach until it reaches\n        // n\n        while ((reach <= n)) {\n            // if we exceed the value present in array\n            if (i < nums.size() && nums[i] <= reach) {\n                // we\'ll add our array value\n                reach += nums[i++];\n            } else {\n                // else we\'ll keep adding ourself to reach (N)\n                reach += reach;\n                // If we add ourself mean we added a number to array hence we\n                // inc our patches count\n                patches++;\n            }\n        }\n        return patches;\n    }\n};\n```\n``` JAVASCRIPT []\nvar minPatches = function (nums, n) {\n    // REACH is number up to which we can add our number and got value\n    let reach = 1;\n    let i = 0;\n    let patches = 0;\n\n    // we have to go up to given n so we\'ll loop for reach until it reaches n  \n    while (reach <= n) {\n        // if we exceed the value present in array \n        if (i < nums.length && nums[i] <= reach) {\n            // we\'ll add our array value \n            reach += nums[i++];\n        } else {\n            // else we\'ll keep adding ourself to reach (N)\n            reach += reach;\n            // If we add ourself mean we added a number to array hence we inc our patches count\n            patches++;\n        }\n    }\n\n    return patches;\n};\n```\n```PYTHON []\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        #  REACH is number up to which we can add our number and got value\n        reach = 1\n        i = 0\n        patches = 0\n\n        # we have to go up to given n so we\'ll loop for reach until it reaches n\n        while reach <= n:\n            # if we exceed the value present in array\n            if i < len(nums) and nums[i] <= reach:\n                # we\'ll add our array value\n                reach += nums[i]\n                i += 1\n            else:\n                # else we\'ll keep adding ourself to reach (N)\n                reach += reach\n                # f we add ourself mean we added a number to array hence we inc our patches count\n                patches += 1\n\n        return patches\n\n```\n```C []\nint minPatches(int* nums, int numsSize, int n) {\n    // REACH is number up to which we can add our number and got value\n    long long reach = 1;\n    long long patches = 0;\n    long i = 0;\n\n    // we have to go up to given n so we\'ll loop for reach until it reaches n\n    while ((reach <= n)) {\n        // if we exceed the value present in array\n        if (i < numsSize && nums[i] <= reach) {\n            // we\'ll add our array value\n            reach += nums[i++];\n        } else {\n            // else we\'ll keep adding ourself to reach (N)\n            reach += reach;\n            // If we add ourself mean we added a number to array hence we inc\n            // our patches count\n            patches++;\n        }\n    }\n    return patches;\n}\n```\n\n---\n# \uD83E\uDD42\u2728\uD83E\uDDC1 More solution \uD83C\uDF89\uD83C\uDF82\u2728\uD83C\uDF70\uD83E\uDD73 \n\n## Go To My Profile and access my GIT [Prakhar-002](https://leetcode.com/u/Prakhar-002/)\n\n## JAVA \uD83C\uDF41| PYTHON \uD83C\uDF70| JAVASCRIPT\u2603\uFE0F | C++ \uD83C\uDFB2| C \uD83D\uDC96\n\n![image.png](https://assets.leetcode.com/users/images/cd65a75c-9bd9-4b37-95e8-938ab1cfb2ea_1718515283.0818863.png)\n\n
['Array', 'Greedy', 'C', 'C++', 'Java', 'Python3', 'JavaScript']