3181. Maximum Total Reward Using Operations II LeetCode Solution

In this guide, you will get 3181. Maximum Total Reward Using Operations II LeetCode Solution with the best time and space complexity. The solution to Maximum Total Reward Using Operations II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Total Reward Using Operations II solution in C++
4. Maximum Total Reward Using Operations II solution in Java
5. Maximum Total Reward Using Operations II solution in Python
6. Additional Resources

Problem Statement of Maximum Total Reward Using Operations II

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

3181. Maximum Total Reward Using Operations II LeetCode Solution in C++

class Solution {
 public:
  // Same as 3180. Maximum Total Reward Using Operations I
  int maxTotalReward(vector<int>& rewardValues) {
    constexpr int kPossibleRewards = 100'000;
    // dp[num] := true if reward `num` is achievable
    bitset<kPossibleRewards> dp;
    dp[0] = true;

    ranges::sort(rewardValues);

    for (const int num : rewardValues) {
      bitset<kPossibleRewards> newBits = dp;
      // Remove the numbers >= the current number.
      newBits <<= kPossibleRewards - num;
      newBits >>= kPossibleRewards - num;
      dp |= newBits << num;
    }

    for (int ans = kPossibleRewards - 1; ans >= 0; --ans)
      if (dp[ans])
        return ans;

    throw;
  }
};
/* code provided by PROGIEZ */

3181. Maximum Total Reward Using Operations II LeetCode Solution in Java

import java.math.BigInteger;

class Solution {
  // Same as 3180. Maximum Total Reward Using Operations I
  public int maxTotalReward(int[] rewardValues) {
    BigInteger one = BigInteger.ONE;
    BigInteger dp = one; // the possible rewards (initially, 0 is achievable)

    Arrays.sort(rewardValues);

    for (final int num : rewardValues) {
      // Remove the numbers >= the current number.
      BigInteger maskBitsLessThanNum = one.shiftLeft(num).subtract(one);
      BigInteger bitsLessThanNum = dp.and(maskBitsLessThanNum);
      dp = dp.or(bitsLessThanNum.shiftLeft(num));
    }

    return dp.bitLength() - 1;
  }
}
// code provided by PROGIEZ

3181. Maximum Total Reward Using Operations II LeetCode Solution in Python

class Solution:
  # Same as 3180. Maximum Total Reward Using Operations I
  def maxTotalReward(self, rewardValues: list[int]) -> int:
    dp = 1  # the possible rewards (initially, 0 is achievable)

    for num in sorted(rewardValues):
      # Remove the numbers >= the current number.
      smallerNums = dp & ((1 << num) - 1)
      dp |= smallerNums << num

    return dp.bit_length() - 1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.