You are given an integer array coins of length n which represents the n coins that you own. The value of the ith coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.
Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.
Note that you may have multiple coins of the same value.
Example 1:
Input: coins = [1,3] Output: 2 Explanation: You can make the following values: - 0: take [] - 1: take [1] You can make 2 consecutive integer values starting from 0.
Example 2:
Input: coins = [1,1,1,4] Output: 8 Explanation: You can make the following values: - 0: take [] - 1: take [1] - 2: take [1,1] - 3: take [1,1,1] - 4: take [4] - 5: take [4,1] - 6: take [4,1,1] - 7: take [4,1,1,1] You can make 8 consecutive integer values starting from 0.
Example 3:
Input: coins = [1,4,10,3,1] Output: 20
Constraints:
coins.length == n1 <= n <= 4 * 1041 <= coins[i] <= 4 * 104The idea is to sort the coins array and attempt to create sums starting from 0. Every time we encounter a coin whose value is greater than the current sum plus one, it indicates that we can't create the next consecutive number. By always adding the smallest coin that helps extend the sequence, we can maximize the range of numbers created.
The C solution sorts the input array first. It then initializes a total sum of 0. It iterates through the sorted coins array and continuously adds any coin to the total sum that doesn't create a gap in the range of sums possible. If a coin's value is larger than our current consecutive sum + 1, we break the loop because we cannot create the next number. Finally, the function returns the value of total + 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), not counting the input array since we do in-place operations.
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,447 views views
Watch 9 more video solutions →Practice Maximum Number of Consecutive Values You Can Make with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor