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