Easy C++ Greedy Solution With Explanation
Approach\nTo solve the problem, we can use a greedy algorithm. The key insight is to sort the coins and then iteratively check if the current coin can extend th
# Approach\nTo solve the problem, we can use a greedy algorithm. The key insight is to sort the coins and then iteratively check if the current coin can extend the range of consecutive values we can form.\n\n1. **Sort the Coins**:\n    - First, we sort the array of coins. This allows us to consider the smallest coins first, which helps in forming the smallest possible values consecutively.\n\n2. **Iterate and Extend**:\n    - We initialize a variable `currNum` to 1, which represents the smallest value that we cannot form yet.\n    - We iterate through the sorted coins. For each coin, if the coin\'s value is less than or equal to `currNum`, it means we can use this coin to extend the range of consecutive values we can form. We then add the coin\'s value to `currNum`.\n    - If the coin\'s value is greater than `currNum`, it means there is a gap, and we cannot form `currNum` using the current set of coins. Hence, we return `currNum` as the result.\n\n3. **Return the Result**:\n    - If we can iterate through all the coins without finding a gap, we return `currNum` as the maximum number of consecutive values we can form.\n\n# Complexity\n- Time complexity: $$O(n \\log n)$$ due to the sorting step.\n- Space complexity: $$O(1)$$ as we are using a constant amount of extra space.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int getMaximumConsecutive(vector<int>& coins) {\n        sort(coins.begin(), coins.end());\n        int currNum = 1;\n\n        for(int i = 0; i < coins.size(); i++){\n            if(coins[i] <= currNum){\n                currNum += coins[i];\n            }\n            else{\n                return currNum;\n            }\n        }\n        return currNum;\n    }\n};\n```\n\n# Example Walkthrough\nLet\'s walk through the example to see how the code works:\n- Input: coins = [1, 1, 1, 4]\n- Output: 8\n\n**Step-by-Step Execution:**\n1. Sort the coins: [1, 1, 1, 4]\n2. Initialize `currNum` to 1.\n3. Iterate through the sorted coins:\n    - For coins[0] = 1: Since 1 <= 1, update `currNum` to 2.\n    - For coins[1] = 1: Since 1 <= 2, update `currNum` to 3.\n    - For coins[2] = 1: Since 1 <= 3, update `currNum` to 4.\n    - For coins[3] = 4: Since 4 <= 4, update `currNum` to 8.\n4. All coins are processed, and the maximum number of consecutive values we can form is 8.\n\nThus, the total number of consecutive integer values that can be made starting from 0 is 8.
['Greedy', 'C++']