Skip to content

2600. K Items With the Maximum Sum

Description

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 the maximum possible sum of numbers written on the items.

 

Example 1:

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:

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

Solutions

Solution 1: Greedy

Thinking

The three labels are fixed. Enumerating how many \(1\)s, \(0\)s, and \(-1\)s we take grows linearly with \(k\). The counts are at most \(50\), so brute force would pass, but it is unnecessary.

The sum is a linear combination of \(1\), \(0\), and \(-1\): taking one more \(1\) is strictly better than taking one more \(0\), which is better than taking one more \(-1\). The unique optimum is therefore to take all \(1\)s first, then \(0\)s, and only then \(-1\)s.

Comparing \(k\) with \(\textit{numOnes}\) and \(\textit{numZeros}\) places us in one of those three cases in constant time, without constructing the selection.

According to the problem description, we should take as many items marked as \(1\) as possible, then take items marked as \(0\), and finally take items marked as \(-1\).

Thus:

  • If the number of items marked as \(1\) in the bag is greater than or equal to \(k\), we take \(k\) items, and the sum of the numbers is \(k\).
  • If the number of items marked as \(1\) is less than \(k\), we take \(\textit{numOnes}\) items, resulting in a sum of \(\textit{numOnes}\). If the number of items marked as \(0\) is greater than or equal to \(k - \textit{numOnes}\), we take \(k - \textit{numOnes}\) more items, keeping the sum at \(\textit{numOnes}\).
  • Otherwise, we take \(k - \textit{numOnes} - \textit{numZeros}\) items from those marked as \(-1\), resulting in a sum of \(\textit{numOnes} - (k - \textit{numOnes} - \textit{numZeros})\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}

 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) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
};

1
2
3
4
5
6
7
8
9
func kItemsWithMaximumSum(numOnes int, numZeros int, numNegOnes int, k int) int {
    if numOnes >= k {
        return k
    }
    if numZeros >= k-numOnes {
        return numOnes
    }
    return numOnes - (k - numOnes - numZeros)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function kItemsWithMaximumSum(
    numOnes: number,
    numZeros: number,
    numNegOnes: number,
    k: number,
): number {
    if (numOnes >= k) {
        return k;
    }
    if (numZeros >= k - numOnes) {
        return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn k_items_with_maximum_sum(
        num_ones: i32,
        num_zeros: i32,
        num_neg_ones: i32,
        k: i32,
    ) -> i32 {
        if num_ones > k {
            return k;
        }

        if num_ones + num_zeros > k {
            return num_ones;
        }

        num_ones - (k - num_ones - num_zeros)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}

Comments