1798

1798. Maximum Number of Consecutive Values You Can Make (Medium)

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: nums = [1,4,10,3,1]
Output: 20

 

Constraints:

• coins.length == n
• 1 <= n <= 4 * 104
• 1 <= coins[i] <= 4 * 104

Related Topics:
Greedy

Similar Questions:

• Patching Array (Hard)

Solution 1. Greedy

// OJ: https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int getMaximumConsecutive(vector<int>& A) {
        int cnt = 1;
        sort(begin(A), end(A));
        for (int n : A) {
            if (n > cnt) break;
            cnt += n;
        }
        return cnt;
    }
};

Note

At first I thought this is a 0-1 knapsack problem which will take O(N * SUM(A)) time. But this will get TLE given the constraints.

// 0-1 knapsack. TLE
class Solution {
public:
    int getMaximumConsecutive(vector<int>& A) {
        long sum = accumulate(begin(A), end(A), 0L), N = A.size();
        vector<bool> dp(sum + 1);
        dp[0] = true;
        for (int i = 0; i < N; ++i) {
            for (long j = sum; j >= A[i]; --j) {
                dp[j] = dp[j] | dp[j - A[i]];
            }
        }
        for (long i = 0; i <= sum; ++i) {
            if (!dp[i]) return i;
        }
        return sum + 1;
    }
};

Then I started to think how to reduce computation. Apparently iterating all the sum is very expensive.

Assume we know what we can get 1, 2, 3, the we get a new number 5, then what are all the numbers we can get? They are 1, 2, 3, 6, 7, 8.

If we represent the numbers using binary mask, then 1, 2, 3 is 111, and 1, 2, 3, 6, 7, 8 is 11100111. It's shifting the previous mask leftwards by 5 and merge with the previous mask. Since the sum could be very large we can't use binary mask here.

Since we only care about the first number that we can't form, we only need to keep track of the maximum number we can form.

Assume we can form [0, cnt) numbers and now we get a new number k, then we can form [k, cnt + k) numbers. As long as k <= cnt, we can extend the range to [0, cnt + k).

When k > cnt, we can't form value cnt, and thus we can only get cnt consecutive numbers