Maximum Total Reward Using Operations II
HardPrompt
You are given an integer array rewardValues of length n, representing the values of rewards.
Initially, your total reward x is 0, and all indices are unmarked. You are allowed to perform the following operation any number of times:
- Choose an unmarked index
ifrom the range[0, n - 1]. - If
rewardValues[i]is greater than your current total rewardx, then addrewardValues[i]tox(i.e.,x = x + rewardValues[i]), and mark the indexi.
Return an integer denoting the maximum total reward you can collect by performing the operations optimally.
Example 1:
Input: rewardValues = [1,1,3,3]
Output: 4
Explanation:
During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.
Example 2:
Input: rewardValues = [1,6,4,3,2]
Output: 11
Explanation:
Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.
Constraints:
1 <= rewardValues.length <= 5 * 1041 <= rewardValues[i] <= 5 * 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to determine all possible reward sums that can be achieved. The core idea is based on the observation that if a set of rewards is collectible, it is always possible to collect them in increasing order of their value. This simplifies the problem significantly, as we can process the rewards one by one after sorting them.
We maintain a boolean array, possible, where possible[x] is true if a total reward of x is achievable. The maximum size of this array is bounded by 2 * max(rewardValues), which is a key insight to make the state space of the DP manageable in terms of memory.
Algorithm
- Sort the
rewardValuesarray in non-decreasing order. - To handle duplicate reward values correctly and efficiently, create a new array
uniqueRewardscontaining only the distinct values fromrewardValues. - Determine the maximum possible sum. If the last reward taken is
rand the sum before that wasx, the final sum isx+r. The conditionr > ximpliesx+r < 2r. Thus, the maximum possible total reward is less than2 * max(rewardValues). - Initialize a boolean array
possibleof size2 * max(rewardValues). Setpossible[0] = trueto represent the initial state of having a total reward of 0. All other elements are initialized tofalse. - Keep track of the highest sum achieved so far, say
highestPossible, initialized to 0. - Iterate through each reward
rinuniqueRewards. - For each
r, iterate through the already possible sumsxfromhighestPossibledown to 0. - If
possible[x]is true andx < r, it means we can take the rewardrto form a new achievable sumx + r. Setpossible[x + r] = trueand updatehighestPossible = max(highestPossible, x + r). - The downward iteration for
xis important to ensure that we only use rewards from previous steps to form new sums with the current rewardr. - After iterating through all unique rewards, the final value of
highestPossibleis the maximum total reward.
Walkthrough
import java.util.Arrays; class Solution { public int maxTotalReward(int[] rewardValues) { Arrays.sort(rewardValues); // Remove duplicates as processing the same value multiple times is redundant for this logic int n = rewardValues.length; int[] uniqueRewards = new int[n]; int uSize = 0; if (n > 0) { uniqueRewards[uSize++] = rewardValues[0]; for (int i = 1; i < n; i++) { if (rewardValues[i] != rewardValues[i-1]) { uniqueRewards[uSize++] = rewardValues[i]; } } } int maxVal = uSize > 0 ? uniqueRewards[uSize - 1] : 0; if (maxVal == 0) return 0; boolean[] possible = new boolean[2 * maxVal]; possible[0] = true; int highestPossible = 0; for (int i = 0; i < uSize; i++) { int r = uniqueRewards[i]; // Iterate downwards to avoid using the current reward `r` multiple times in this step. // We only need to check sums up to `r-1`. for (int x = Math.min(highestPossible, r - 1); x >= 0; x--) { if (possible[x]) { if (x + r < 2 * maxVal) { possible[x + r] = true; highestPossible = Math.max(highestPossible, x + r); } } } } return highestPossible; }}Complexity
Time
O(N log N + U * V_max), where `N` is the number of rewards, `U` is the number of unique rewards, and `V_max` is the maximum reward value. Sorting takes `O(N log N)`. The nested loops can take up to `O(U * V_max)` time in the worst case, which is too slow for the given constraints.
Space
O(V_max), where `V_max` is the maximum value in `rewardValues`. This is for the `possible` boolean array.
Trade-offs
Pros
Conceptually straightforward and easier to implement compared to more optimized solutions.
Correctly solves the problem for smaller constraints.
Cons
The time complexity is too high for the given constraints, leading to a 'Time Limit Exceeded' error on larger test cases.
Solutions
Solution
import java.math.BigInteger ; import java.util.Arrays ; class Solution { public int maxTotalReward ( int [] rewardValues ) { int [] nums = Arrays . stream ( rewardValues ). distinct (). sorted (). toArray (); BigInteger f = BigInteger . ONE ; for ( int v : nums ) { BigInteger mask = BigInteger . ONE . shiftLeft ( v ). subtract ( BigInteger . ONE ); BigInteger shifted = f . and ( mask ). shiftLeft ( v ); f = f . or ( shifted ); } return f . bitLength () - 1 ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.