Binary Search || Code With Comments || Super Easy
Intuition\n\nThe code is well commented. This is the intuition for isPossible function in the code first read the comments in the code to get a better understan
# Intuition\n\n**The code is well commented. This is the intuition for isPossible function in the code first read the comments in the code to get a better understanding**\n\nThe isPossible Function in my code is based on the fact that if we have n consequtive numbers starting from 1,\nthen we can make each and every sum from 1 to (n)*(n+1)/2 with that numbers only\neg [1,2,3,4,5] we can make sums from [1, 15] both inclusive,\nnow if we have a missing number eg 3 is missing\neg [1,2,4,5] we can make upto [1, 15-missingNumber] ie [1, 15-3] ie [1,12]\n\nwe will take the range variable for counting the range\n\nwe will take totalSum for calculating the totalSum\n\nwhenever we will not find a number that is greater than range+1 we will always add range+1 in our range to maintain that consequtive nature of out sequence\n\nand if range is 10 and we found 9 we ll update our range simply as 19\nbut if we find 12 we will make our range as range = range+range+1\nie 10+10+1 = 21 ie (10+11)\n\nthat simple \n\nif we found range+1 in our nums then no increase in patches\nif we dont please increase the patch by one\n\nif the patches are less than or equal to the required patches\nreturn true else return false\n\nrest will be held by binary search\n\nPlease upvote :)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```\n#define ll long long\n\nclass Solution {\npublic:\n\n    vector<ll> nums;\n    ll TOTALSUM;\n\n    bool isPossible(int nop, ll n)\n    {\n        ll totalSum = TOTALSUM;\n\n        int reqPatch = 0;\n        ll range = 0;\n        int i = 0;\n\n        while(i<nums.size())\n        {\n            if(nums[i]<=(range+1))\n            {\n                range = range + nums[i];\n                i++;\n            }\n            else\n            {\n                while(nums[i]>(range+1))\n                {\n                    reqPatch++;\n                    totalSum = totalSum + range + 1;\n                    range = range + range + 1;\n                }\n            }\n        }\n\n        while(range<n)\n        {\n            reqPatch++;\n            totalSum = totalSum + range + 1;\n            range = range + range + 1;\n        }\n\n        if(totalSum<n)\n        {\n            reqPatch++;\n        }\n\n        if(reqPatch<=nop)\n        {\n            return true;\n        }\n        else\n        {\n            return false;\n        }\n\n    }\n\n    int minPatches(vector<int>& N, int n) {\n        bool flag = false;\n\n        //if one is not present include 1\n        if(N[0]!=1)\n        {\n            nums.push_back(1);\n            TOTALSUM+=1;\n            flag = true;\n        }\n\n        //if n==1 then special case\n        if(n==1)\n        {\n            if(flag==true)\n            {\n                return 1;\n            }\n            else\n            {\n                return 0;\n            }\n        }\n\n        //exclude all those numbers which are greater than n\n        for(int i=0;i<N.size();i++)\n        {\n            if(N[i]<n)\n            {\n                nums.push_back(N[i]);\n                TOTALSUM+=N[i];\n            }\n        }\n\n        //initialize the binary search\n        int high = n;\n        int low = 0;\n\n        int ans = high;\n\n        //carry out binary search\n        while(low<=high)\n        {\n            int mid = (high+low)/2;\n            if(isPossible(mid, n))\n            {\n                ans = mid;\n                high = mid-1;\n            }\n            else\n            {\n                low = mid+1;\n            }\n        }\n\n        if(flag==true)\n        {\n            ans++;\n        }\n\n        return ans;\n    }\n};\n```
['Binary Search', 'C++']