3181. Maximum Total Reward Using Operations II

HardBit ManipulationArrayDynamic Programming

Problem Description

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.

Intuition

The problem requires us to maximize the total reward by adding values from the rewardValues array, but there is a twist: we can only add a particular value if it exceeds the current total. This essentially forms a challenge of choosing the right sequence of indices to mark such that the total reward is maximized.

The approach to solving this involves converting the challenge into a dynamic programming problem using bit manipulation. Here's the intuition behind the solution:

Distinct Sorted Values: We first sort the distinct rewardValues. This sorting helps in determining a sequence where each selected reward can potentially add up to our total reward optimally since larger values can be used later as they will more likely be greater than the current reward total.
Bit Masking and DP: We use a bitmask to keep track of all possible reward totals. If the i-th bit in this mask is set to 1, it means that a total reward of i is achievable with the selected rewards.
State Transition: For each value v in the sorted set of reward values, we update our bitmask (f). The transition involves checking which parts of the current bitmask can be shifted by v positions to represent new achievable totals. This is done using the operation (f & ((1 << v) - 1)) << v, ensuring efficient manipulation of potential reward totals.
Result Calculation: Finally, the highest set bit in the bitmask gives the maximum possible reward total, which is returned as the solution.

This bit manipulation technique efficiently handles the dynamic programming state transitions and yields the optimal result.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem uses a combination of dynamic programming and bit manipulation to efficiently determine the maximum total reward. Here’s a detailed walkthrough of the implementation:

Initial Setup:
- We begin by sorting the distinct values in rewardValues. This helps in deciding which rewards to add based on their ability to exceed the current total reward.
Bitmask Representation:
- We use a bitmask f, initialized to 1. This bitmask serves as a dynamic programming table in a compressed form, where the i-th bit being set indicates that a total reward of i is achievable with the selected rewards so far.
Dynamic Programming Transition using Bit Manipulation:
- For each reward value v in this sorted sequence, we examine how adding v affects the possible reward totals.
- The bit manipulation operation (f & ((1 << v) - 1)) << v effectively takes all achievable totals that are less than v and considers what new totals become achievable if we add v to these. The original f holds the existing achievable totals.
- The OR operation |= updates f with these new possibilities.
Result Extraction:
- After processing all the reward values, the highest bit set in f gives the maximum obtainable total reward. The method f.bit_length() - 1 efficiently finds this maximum set bit, which represents the largest total reward achievable.

By combining sorting, dynamic programming, and bit manipulation, this approach optimizes both space and time efficiency, effectively handling even the upper ranges of data input sizes.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach:

Consider the rewardValues array: [3, 1, 4, 2].

Initial Setup:

Sort Distinct Values: First, sort the array to get [1, 2, 3, 4].

Bitmask Representation: 2. Initialize Bitmask: Start with a bitmask f = 1 (which in binary is 0001). This indicates that a total of 0 is initially achievable.

Dynamic Programming Transition using Bit Manipulation: 3. Process Each Value:

For v = 1:
- Calculate (f & ((1 << 1) - 1)) << 1, which is (0001 & 0001) << 1 = 0010.
- Update f with OR operation: f |= 0010 results in f = 0011.
- Now, totals 0 and 1 are achievable.
For v = 2:
- Calculate (f & ((1 << 2) - 1)) << 2, which is (0011 & 0011) << 2 = 1100.
- Update f: f |= 1100 results in f = 1111.
- Now, totals 0, 1, 2, and 3 are achievable.
For v = 3:
- Calculate (f & ((1 << 3) - 1)) << 3, which is (1111 & 0111) << 3 = 111000.
- Update f: f |= 111000 results in f = 111111.
- Totals from 0 to 5 are now achievable.
For v = 4:
- Calculate (f & ((1 << 4) - 1)) << 4, which is (111111 & 1111) << 4 = 11110000.
- Update f: f |= 11110000 results in f = 11111111.
- Totals from 0 to 7 are achievable.

Result Extraction: 4. Find Maximum Reward:

The highest set bit in f = 11111111 corresponds to 7, which is calculated using f.bit_length() - 1.
Thus, the maximum total reward obtainable is 7.

This example illustrates how the bitmask dynamically captures the achievable totals by incrementally adding the sorted reward values.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxTotalReward(self, rewardValues: List[int]) -> int:
5        # Get unique reward values and sort them
6        unique_rewards = sorted(set(rewardValues))
7
8        # Initialize a bit mask with the first bit set
9        bit_mask = 1
10
11        # Iterate over each unique reward value
12        for value in unique_rewards:
13            # Update the bit mask by shifting it left by 'value' positions
14            # and logically OR it with previous bit masks up to 'value - 1'
15            bit_mask |= (bit_mask & ((1 << value) - 1)) << value
16
17        # Count the number of bits needed to represent 'bit_mask' and subtract 1
18        return bit_mask.bit_length() - 1
19

1import java.math.BigInteger;
2import java.util.Arrays;
3
4class Solution {
5    public int maxTotalReward(int[] rewardValues) {
6        // Remove duplicates from 'rewardValues', sort the distinct values, and store them in 'nums'.
7        int[] nums = Arrays.stream(rewardValues).distinct().sorted().toArray();
8      
9        // Initialize a BigInteger 'f' with value 1, which will be used to track possible rewards.
10        BigInteger f = BigInteger.ONE;
11      
12        // Iterate over each unique value in 'nums'.
13        for (int value : nums) {
14            // Create a bitmask that has 'value' number of bits set to 1.
15            BigInteger mask = BigInteger.ONE.shiftLeft(value).subtract(BigInteger.ONE);
16            // Shift the bits in 'f' by 'value' positions and perform a bitwise AND with the mask.
17            BigInteger shifted = f.and(mask).shiftLeft(value);
18            // Update 'f' by setting the bits where 'shifted' has bits set, using a bitwise OR.
19            f = f.or(shifted);
20        }
21      
22        // Return the highest bit index set in 'f', which represents the maximum achievable reward.
23        return f.bitLength() - 1;
24    }
25}
26

1#include <vector>
2#include <algorithm>
3#include <bitset>
4
5class Solution {
6public:
7    int maxTotalReward(std::vector<int>& rewardValues) {
8        // Sort the reward values to facilitate duplicate removal and bit manipulation
9        std::sort(rewardValues.begin(), rewardValues.end());
10
11        // Remove duplicate reward values
12        rewardValues.erase(std::unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
13
14        // Initialize a bitset to track achievable sum combinations; set the zero-sum as achievable
15        std::bitset<100000> f{1};
16
17        // For each reward value, update the bitset to include new achievable sums
18        for (int value : rewardValues) {
19            int shift = f.size() - value; // Calculate the shift amount for the bitset
20            // Update the bitset: shift left by 'shift', shift right by 'shift - value', and update with OR
21            f |= f << shift >> (shift - value);
22        }
23
24        // Check from the highest potential sum downwards to find the maximum achievable sum
25        for (int i = rewardValues.back() * 2 - 1;; i--) {
26            if (f.test(i)) {
27                return i; // Return the maximum achievable sum
28            }
29        }
30    }
31};
32

1// Function to calculate the maximum total reward based on unique reward values.
2function maxTotalReward(rewardValues: number[]): number {
3    // Sort the reward values in ascending order.
4    rewardValues.sort((a, b) => a - b);
5  
6    // Remove duplicates by converting the array to a Set and back to an array.
7    rewardValues = [...new Set(rewardValues)];
8  
9    // Initialize 'f' as a BigInt with an initial value of 1.
10    let f = 1n;
11  
12    // Iterate through each unique reward value.
13    for (const value of rewardValues) {
14        // Calculate the mask by shifting 1 to the left by 'value' positions and subtracting 1.
15        const mask = (1n << BigInt(value)) - 1n;
16      
17        // Update 'f' by OR'ing it with a left-shifted version of itself masked by 'mask'.
18        f = f | ((f & mask) << BigInt(value));
19    }
20  
21    // Convert 'f' to its binary representation, find its length, and subtract 1.
22    return f.toString(2).length - 1;
23}
24

Time and Space Complexity

The time complexity of the code is O(n \times M / w), where n is the length of the rewardValues array, M is twice the maximum value in the rewardValues array, and w is the width of the integer, typically 32 or 64. This complexity arises because the code iterates over the sorted unique values of rewardValues, and for each value, it performs a bitwise operation that deals with shifting bits v times (where v is the reward value), leading to time complexity dependent on the maximum value.

The space complexity is O(n + M / w), where n is the number of unique values in rewardValues (for storing them in nums) and M / w accounts for the space needed for the bit manipulation operations, particularly the value f, which holds a bitmask indicating possible sums that can be attained. The space complexity is relatively efficient given that it combines the array size and the bits needed to represent potential sums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: