C++ | Short Iterative Greedy solution | Explained | Fast solution with less memory usage
Intuition\n Describe your first thoughts on how to solve this problem. \nNote: For complete code, please scroll to the end. Detailed explanation continues below
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n***Note:*** *For complete code, please scroll to the end. Detailed explanation continues below.*\n\nSuppose we have already achieved a value of x. Now our next coin can be either equal to x+1 or less/greater than x+1. If our next coin is equal to x+1 then we can surely form x+1 amount using that coin alone. However, if our next coin is not equal to x+1 then either we can form x+1 using our next coin and some previous coin(s) or we can\'t form it.\n\nNow in case our next coin is greater than x+1, then we can\'t form our next value as that will require subtracting some amount from next coin which is not possible as we can only use a specific coin or sum of some coins and we also already know no combination of our previous coins can give next value.\n\nIn case our next coin is less than x+1, then we have to make sure that the difference in amount can be made up from our remaining coins. It it can be then we can proceed else we can\'t.\n\nAlso when proceeding, if we have a value x and we can form x+1 using either next coin alone or in combination with some other coins, then we can also form till x+(the value of next coin) as:\n\nWe have been checking in a contiguous manner for the maximum sum possible. So for a coin value of v, we can combine it with previous coins to make sums of (v+1),(v+2),(v+3)........(v+x) where x is the previous value we have achieved till now without considering the coin with value v.\n\nAlso note that we will be starting with 0 as max value as that is the least value we can achieve anytime as it will not require any coins and then we will keep increasing on this.\n\n# Detailed Explanation/Approach\n<!-- Describe your approach to solving the problem. -->\nFirst we sort the input as we will be starting from 0 and incrementing our maximum value in every iteration in an increasing manner. Our maximum value will be maintained in the variable val. Also for our iteration we take the total size of our input in size variable.\n```\nsort(coins.begin(),coins.end());\nint val=0;\nint size=coins.size();\n```\nNow we will loop over our coins input and keep increasing the value of val. Only if we either reach the end of our input or if we can\'t increase the value of val to the next value we need to achieve(which is previous value + 1), then we will break from the loop.\n```\nfor(int i=0;i<size;i++){\n            if(.......)\n             .....\n            else\n             break;\n        }\n```\nHere, we determine we can achieve next value if any of the below condition satisfies:\n1. The next coin value is equal to the next value we want to achieve:`coins[i]==val+1`\n2. The next coin value is less than our next required value:`coins[i]<val+1` and the difference between the next required value and our next coin value can be made up using previous coins (i.e is less than or equal to our current max value): `(val+1)-coins[i]<=val`\nIf none of the above conditions satisfy then we can\'t achieve our next value and we break from the loop.\n```\nfor(int i=0;i<size;i++){\n            if(coins[i]==val+1 || (coins[i]<val+1 && (val+1)-coins[i]<=val))\n             ....\n            else\n             break;\n        }\n```\nIf we can achieve our next value, then we increase our max value variable  val by the value of the next coin(i.e our max value becomes the sum of our next coin value and current max value), as we can also achieve in this case the values upto the sum of our coin value and current max value.\n```\nfor(int i=0;i<size;i++){\n            if(coins[i]==val+1 || (coins[i]<val+1 && (val+1)-coins[i]<=val))\n             val+=coins[i];\n            else\n             break;\n        }\n```\nFinally we have our max achievable value in the val variable. However, the problem is asking for the maximum number of **consecutive integers** we can form. This means that we have to count all the integers from 0 till our max value which is simply equal to our max value+1. So we return val+1.\n```\nreturn val+1;\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nIn our program we are using only 1 for loop for iterating over all the input elements only once which should make our TC O(n). However, for sorting we are using an inbuilt function, which basically does a quicksort (we can also implemenet this ourselves instead of using library function). This makes the total TC O(n^2) in worst case and O(nlogn) in average and best cases.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe are not using any other extra space except our variables that hold the max value and the input size. But these take constant space. So our total SC is O(1).\n\n# Complete Code\n```\nint getMaximumConsecutive(vector<int>& coins) {\n        sort(coins.begin(),coins.end());\n        int val=0;\n        int size=coins.size();\n        for(int i=0;i<size;i++){\n            if(coins[i]==val+1 || (coins[i]<val+1 && (val+1)-coins[i]<=val))\n             val+=coins[i];\n            else\n             break;\n        }\n        return val+1;\n}\n```\n![image.png](https://assets.leetcode.com/users/images/7e2c118a-6aa6-44a0-a0c1-455c21dfdb57_1671666110.025807.png)\n\n![image.png](https://assets.leetcode.com/users/images/339a6107-201a-4d82-94fd-baafb5b3f144_1671666147.8950372.png)\n\nIf this helped you, please leave an upvote. Thanks. \uD83D\uDE0A\uD83C\uDF08\n
['C++']