Problem

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.

You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:

  • numOnes items with 1s written on them.
  • numZeroes items with 0s written on them.
  • numNegOnes items with -1s written on them.

We want to pick exactly k items among the available items. Return themaximum possible sum of numbers written on the items.

Examples

Example 1

1
2
3
4

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
Output: 2
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.

Example 2

1
2
3
4

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
Output: 3
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.

Constraints

  • 0 <= numOnes, numZeros, numNegOnes <= 50
  • 0 <= k <= numOnes + numZeros + numNegOnes

Solution

Method 1 – Greedy Selection

Intuition

To maximize the sum, always pick as many 1’s as possible, then 0’s, and only pick -1’s if needed. This is because 1 > 0 > -1, and we want the largest possible sum.

Approach

  1. Take as many 1’s as possible, up to k.
  2. If k is not exhausted, take as many 0’s as possible (they don’t affect the sum).
  3. If k is still not exhausted, take -1’s for the remaining picks (each reduces the sum by 1).
  4. Return the resulting sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int ans = 0;
        int take1 = min(numOnes, k);
        ans += take1;
        k -= take1;
        int take0 = min(numZeros, k);
        k -= take0;
        ans -= k; // remaining k are -1's
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func kItemsWithMaximumSum(numOnes int, numZeros int, numNegOnes int, k int) int {
    ans := 0
    take1 := min(numOnes, k)
    ans += take1
    k -= take1
    take0 := min(numZeros, k)
    k -= take0
    ans -= k
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int ans = 0;
        int take1 = Math.min(numOnes, k);
        ans += take1;
        k -= take1;
        int take0 = Math.min(numZeros, k);
        k -= take0;
        ans -= k;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun kItemsWithMaximumSum(numOnes: Int, numZeros: Int, numNegOnes: Int, k: Int): Int {
        var ans = 0
        var rem = k
        val take1 = minOf(numOnes, rem)
        ans += take1
        rem -= take1
        val take0 = minOf(numZeros, rem)
        rem -= take0
        ans -= rem
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        ans = min(numOnes, k)
        k -= ans
        take0 = min(numZeros, k)
        k -= take0
        ans -= k
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn k_items_with_maximum_sum(num_ones: i32, num_zeros: i32, num_neg_ones: i32, k: i32) -> i32 {
        let mut ans = num_ones.min(k);
        let mut rem = k - ans;
        let take0 = num_zeros.min(rem);
        rem -= take0;
        ans -= rem;
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    kItemsWithMaximumSum(numOnes: number, numZeros: number, numNegOnes: number, k: number): number {
        let ans = Math.min(numOnes, k);
        k -= ans;
        let take0 = Math.min(numZeros, k);
        k -= take0;
        ans -= k;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(1), as all operations are simple arithmetic and comparisons.
  • 🧺 Space complexity: O(1), as only a constant amount of space is used.