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

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