Teaching Kids Programming – K Items With the Maximum Sum | ninjasquad

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

https://www.youtube.com/watch?v=Pszd9P_i5fo

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

### Teaching Kids Programming – K Items With the Maximum Sum

We can construct the sorted array, and then pick the K items exactly from the right to the left. This has the time complexity of O(N) where N is the total number (equals to Ones + Zeros + Negative-Ones). And the space complexity is also O(N) as we need to prepare such an array.

1 2 3 4 5 6 |
class Solution: def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: if k == 0: return 0 a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1] return sum(a[-k:]) |

class Solution: def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: if k == 0: return 0 a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1] return sum(a[-k:])

A special case is when K is zero, we return 0, otherwise we use the list comprehension to return the sum of the last K numbers of the constructed sorted array (that contains numNegOnes -1, numZeros 0, and numOnes 1).

A faster approach/algorithm would be to compute the ones we have (as we pick them first), then subtract the negative ones which is max(0, k-numZeros-numOnes). If k is exceeding the amount of zeros plus ones, then we have to minus the amount of negative ones. The time/space complexity is O(1) constant.

1 2 3 |
class Solution: def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: return min(k, numOnes) - max(0, k - numZeros - numOnes) |

class Solution: def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: return min(k, numOnes) - max(0, k - numZeros - numOnes)

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

545 words

**Last Post**: Introduction to Ledger Virtual Crypto Card

Source: Internet