3180. Maximum Total Reward Using Operations I LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3180. Maximum Total Reward Using Operations I LeetCode Solution with the best time and space complexity. The solution to Maximum Total Reward Using Operations I 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.

Problem Statement
Complexity Analysis
Maximum Total Reward Using Operations I solution in C++
Maximum Total Reward Using Operations I solution in Java
Maximum Total Reward Using Operations I solution in Python
Additional Resources

3180. Maximum Total Reward Using Operations I LeetCode Solution image

Problem Statement of Maximum Total Reward Using Operations I

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 <= 2000
1 <= rewardValues[i] <= 2000

Complexity Analysis

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

3180. Maximum Total Reward Using Operations I LeetCode Solution in C++

// According to the constraint rewardValues[i] <= 5 * 10^4, the maximum total
// reward < 2 * (5 * 10^4) = 10^5. We can use bitset to record whether each
// `rewardValue` is achievable in O(1).
//
// Let's use `rewardValues = [1, 3, 4]` as an example.
//
// The maximum reward is 4, so the maximum possible total < 2 * 4 = 8.
// Therefore, we can set the size of the bitset to 8 to represent possible
// total rewards from 0 to 7.
//
// Let's define a bitset `dp` to record whether each total reward is
// achievable. dp[num] = true if reward `num` is achievable.
//
// Initially, dp = 0b00000001 := reward 0 is achievable.
//
// * rewardValues[0] = 1, for each dp[i] = 1, where i + 1 < 10, dp[i + 1] = 1.
//   => dp = 0b00000011 := rewards 0 and 1 are achievable.
//
// * rewardValues[1] = 3, for each dp[i] = 1, where i + 3 < 10, dp[i + 3] = 1.
//   => dp = 0b00011011 := rewards 0, 1, 3, and 4 are achievable.
//
// * rewardValues[2] = 4, for each dp[i] = 1, where i + 4 < 10, dp[i + 4] = 1.
//   => dp = 0b10011011 := rewards 0, 1, 3, 4, 5, and 7 are achievable.
//
// Therefore, the maximum total reward is 7.

class Solution {
 public:
  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 */

3180. Maximum Total Reward Using Operations I LeetCode Solution in Java

// According to the constraint rewardValues[i] <= 5 * 10^4, the maximum total
// reward < 2 * (5 * 10^4) = 10^5. We can use bitset to record whether each
// `rewardValue` is achievable in O(1).
//
// Let's use `rewardValues = [1, 3, 4]` as an example.
//
// The maximum reward is 4, so the maximum possible total < 2 * 4 = 8.
// Therefore, we can set the size of the bitset to 8 to represent possible
// total rewards from 0 to 7.
//
// Let's define a bitset `dp` to record whether each total reward is
// achievable. dp[num] = true if reward `num` is achievable.
//
// Initially, dp = 0b00000001 := reward 0 is achievable.
//
// * rewardValues[0] = 1, for each dp[i] = 1, where i + 1 < 10, dp[i + 1] = 1.
//   => dp = 0b00000011 := rewards 0 and 1 are achievable.
//
// * rewardValues[1] = 3, for each dp[i] = 1, where i + 3 < 10, dp[i + 3] = 1.
//   => dp = 0b00011011 := rewards 0, 1, 3, and 4 are achievable.
//
// * rewardValues[2] = 4, for each dp[i] = 1, where i + 4 < 10, dp[i + 4] = 1.
//   => dp = 0b10011011 := rewards 0, 1, 3, 4, 5, and 7 are achievable.
//
// Therefore, the maximum total reward is 7.

import java.math.BigInteger;

class Solution {
  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

3180. Maximum Total Reward Using Operations I LeetCode Solution in Python

# According to the constraint rewardValues[i] <= 5 * 10^4, the maximum total
# reward < 2 * (5 * 10^4) = 10^5. We can use bitset to record whether each
# `rewardValue` is achievable in O(1).
#
# Let's use `rewardValues = [1, 3, 4]` as an example.
#
# The maximum reward is 4, so the maximum possible total < 2 * 4 = 8.
# Therefore, we can set the size of the bitset to 8 to represent possible
# total rewards from 0 to 7.
#
# Let's define a bitset `dp` to record whether each total reward is
# achievable. dp[num] = true if reward `num` is achievable.
#
# Initially, dp = 0b00000001 := reward 0 is achievable.
#
# * rewardValues[0] = 1, for each dp[i] = 1, where i + 1 < 10, dp[i + 1] = 1.
#   => dp = 0b00000011 := rewards 0 and 1 are achievable.
#
# * rewardValues[1] = 3, for each dp[i] = 1, where i + 3 < 10, dp[i + 3] = 1.
#   => dp = 0b00011011 := rewards 0, 1, 3, and 4 are achievable.
#
# * rewardValues[2] = 4, for each dp[i] = 1, where i + 4 < 10, dp[i + 4] = 1.
#   => dp = 0b10011011 := rewards 0, 1, 3, 4, 5, and 7 are achievable.
#
# Therefore, the maximum total reward is 7.

class Solution:
  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

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

Table of Contents