Maximum Total Reward Using Operations II

Hard

#2826Time: 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.1 company

Patterns

Dynamic Programming Bit Manipulation

Data structures

Array

Companies

Mitsogo

Prompt

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 i from the range [0, n - 1].
If rewardValues[i] is greater than your current total reward x, then add rewardValues[i] to x (i.e., x = x + rewardValues[i]), and mark the index i.

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 * 10⁴
1 <= rewardValues[i] <= 5 * 10⁴

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 rewardValues array in non-decreasing order.
To handle duplicate reward values correctly and efficiently, create a new array uniqueRewards containing only the distinct values from rewardValues.
Determine the maximum possible sum. If the last reward taken is r and the sum before that was x, the final sum is x+r. The condition r > x implies x+r < 2r. Thus, the maximum possible total reward is less than 2 * max(rewardValues).
Initialize a boolean array possible of size 2 * max(rewardValues). Set possible[0] = true to represent the initial state of having a total reward of 0. All other elements are initialized to false.
Keep track of the highest sum achieved so far, say highestPossible, initialized to 0.
Iterate through each reward r in uniqueRewards.
For each r, iterate through the already possible sums x from highestPossible down to 0.
If possible[x] is true and x < r, it means we can take the reward r to form a new achievable sum x + r. Set possible[x + r] = true and update highestPossible = max(highestPossible, x + r).
The downward iteration for x is important to ensure that we only use rewards from previous steps to form new sums with the current reward r.
After iterating through all unique rewards, the final value of highestPossible is the maximum total reward.

Walkthrough

1import java.util.Arrays;2 3class Solution {4    public int maxTotalReward(int[] rewardValues) {5        Arrays.sort(rewardValues);6        7        // Remove duplicates as processing the same value multiple times is redundant for this logic8        int n = rewardValues.length;9        int[] uniqueRewards = new int[n];10        int uSize = 0;11        if (n > 0) {12            uniqueRewards[uSize++] = rewardValues[0];13            for (int i = 1; i < n; i++) {14                if (rewardValues[i] != rewardValues[i-1]) {15                    uniqueRewards[uSize++] = rewardValues[i];16                }17            }18        }19 20        int maxVal = uSize > 0 ? uniqueRewards[uSize - 1] : 0;21        if (maxVal == 0) return 0;22        23        boolean[] possible = new boolean[2 * maxVal];24        possible[0] = true;25        26        int highestPossible = 0;27 28        for (int i = 0; i < uSize; i++) {29            int r = uniqueRewards[i];30            // Iterate downwards to avoid using the current reward `r` multiple times in this step.31            // We only need to check sums up to `r-1`.32            for (int x = Math.min(highestPossible, r - 1); x >= 0; x--) {33                if (possible[x]) {34                    if (x + r < 2 * maxVal) {35                        possible[x + r] = true;36                        highestPossible = Math.max(highestPossible, x + r);37                    }38                }39            }40        }41        42        return highestPossible;43    }44}

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.

This approach enhances the dynamic programming solution by using bitmasks for a significant performance boost. The set of achievable sums is represented by a bitmask (e.g., a long[] array), where the i-th bit is set if a sum of i is possible.

The key operation is updating this bitmask. For a given reward r, we want to add r to all existing achievable sums x where x < r. In the world of bitmasks, this translates to taking the portion of the achieved bitmask representing sums less than r, left-shifting it by r positions, and then OR-ing it with the original achieved bitmask. This bit-level parallelism allows us to update many states simultaneously, drastically reducing the runtime compared to iterating through each sum one by one.

Algorithm

First, sort the rewardValues array and then extract the unique values into a new array, uniqueRewards. This is because for any given achievable sum x, a reward value r can be added at most once, so processing the same r multiple times is redundant.
The maximum possible sum is less than 2 * V_max, where V_max is the maximum reward value. We create a bitmask, implemented as a long[] array named achieved, to store the achievable sums. The size of this array will be (2 * V_max) / 64 + 2.
Initialize the bitmask by setting the bit for sum 0: achieved[0] = 1L.
Iterate through each unique reward r from uniqueRewards.
For each r, we need to perform the operation: achieved |= (achieved_lt_r << r), where achieved_lt_r is a bitmask of all achievable sums strictly less than r.
This operation is implemented by:
1. Creating a temporary bitmask (sumsToShift) that is a copy of the achieved bitmask, but only for bits corresponding to sums less than r. This involves copying the first (r-1)/64 words and masking the last word.
2. Shifting this temporary bitmask sumsToShift left by r positions. This is done by calculating a wordShift = r / 64 and a bitShift = r % 64 and applying them to each long in sumsToShift.
3. Performing a bitwise OR of the shifted result back into the main achieved bitmask.
After iterating through all unique rewards, the final achieved bitmask contains all possible sums. The answer is the index of the highest set bit, which can be found by scanning the long[] array from the end.

Walkthrough

1import java.util.Arrays;2 3class Solution {4    public int maxTotalReward(int[] rewardValues) {5        Arrays.sort(rewardValues);6        int n = rewardValues.length;7        8        int[] uniqueRewards = new int[n];9        int uSize = 0;10        if (n > 0) {11            uniqueRewards[uSize++] = rewardValues[0];12            for (int i = 1; i < n; i++) {13                if (rewardValues[i] != rewardValues[i-1]) {14                    uniqueRewards[uSize++] = rewardValues[i];15                }16            }17        }18 19        int maxVal = uSize > 0 ? uniqueRewards[uSize - 1] : 0;20        if (maxVal == 0) return 0;21        22        int M = 2 * maxVal;23        long[] achieved = new long[M / 64 + 2];24        achieved[0] = 1L; // Sum 0 is achievable25 26        for (int i = 0; i < uSize; i++) {27            int r = uniqueRewards[i];28            29            // 1. Create a temporary bitmask of achievable sums less than r30            int lastWordIdx = (r - 1) / 64;31            long[] sumsToShift = new long[lastWordIdx + 1];32            System.arraycopy(achieved, 0, sumsToShift, 0, lastWordIdx + 1);33            34            long mask = (1L << (r % 64)) - 1;35            if (r % 64 == 0) mask = -1L; // all 1s for a full word36            sumsToShift[lastWordIdx] &= mask;37 38            // 2. Shift this temporary bitmask by r and OR it with 'achieved'39            int wordShift = r / 64;40            int bitShift = r % 64;41            42            for (int k = 0; k < sumsToShift.length; k++) {43                if (sumsToShift[k] == 0) continue;44                long val = sumsToShift[k];45                46                if (bitShift == 0) {47                    achieved[k + wordShift] |= val;48                } else {49                    achieved[k + wordShift] |= (val << bitShift);50                    if (k + wordShift + 1 < achieved.length) {51                        achieved[k + wordShift + 1] |= (val >>> (64 - bitShift));52                    }53                }54            }55        }56 57        // 3. Find the highest achievable sum58        for (int i = M - 1; i >= 0; i--) {59            if ((achieved[i / 64] & (1L << (i % 64))) != 0) {60                return i;61            }62        }63        return 0;64    }65}

Complexity

Time

O(N log N + sum(unique_rewards) / w). Sorting takes `O(N log N)`. The DP update for each unique reward `r` takes `O(r/w)` time. The total time for all updates is proportional to the sum of all unique reward values, divided by the word size `w`. This is efficient enough for the given constraints.

Space

O(V_max / w), where `V_max` is the maximum reward value and `w` is the word size (64 for `long`). This is for the `achieved` bitmask.

Trade-offs

Pros

Highly efficient and passes the given constraints.
Leverages bit-level parallelism to update multiple DP states in a single operation.

Cons

The implementation is more complex due to manual bit manipulation of the long[] array.
Requires a good understanding of bitwise operations and how they translate to array manipulations.

Solutions

Solution

1import 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 ; } }

1class Solution { public: int maxTotalReward ( vector < int >& rewardValues ) { sort ( rewardValues . begin (), rewardValues . end ()); rewardValues . erase ( unique ( rewardValues . begin (), rewardValues . end ()), rewardValues . end ()); bitset < 100000 > f { 1 }; for ( int v : rewardValues ) { int shift = f . size () - v ; f |= f << shift >> ( shift - v ); } for ( int i = rewardValues . back () * 2 - 1 ;; i -- ) { if ( f . test ( i )) { return i ; } } } };

1class Solution : def maxTotalReward ( self , rewardValues : List [ int ]) -> int : nums = sorted ( set ( rewardValues )) f = 1 for v in nums : f |= ( f & (( 1 << v ) - 1 )) << v return f . bit_length () - 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.

← Previous

Previous problem

Next problem