Educating Children Programming – Ok Objects With the Most Sum

Educating Children Programming: Movies on Knowledge Buildings and Algorithms

There’s a bag that consists of things, every merchandise has a number one, 0, or -1 written on it. You’re given 4 non-negative integers numOnes, numZeros, numNegOnes, and okay.

The bag initially incorporates:
numOnes objects with 1s written on them.
numZeroes objects with 0s written on them.
numNegOnes objects with -1s written on them.
We need to choose precisely okay objects among the many out there objects. Return the utmost doable sum of numbers written on the objects.

Instance 1:
Enter: numOnes = 3, numZeros = 2, numNegOnes = 0, okay = 2
Output: 2
Rationalization: We have now a bag of things with numbers written on them {1, 1, 1, 0, 0}. We take 2 objects with 1 written on them and get a sum in a complete of two.
It may be confirmed that 2 is the utmost doable sum.

Instance 2:
Enter: numOnes = 3, numZeros = 2, numNegOnes = 0, okay = 4
Output: 3
Rationalization: We have now a bag of things with numbers written on them {1, 1, 1, 0, 0}. We take 3 objects with 1 written on them, and 1 merchandise with 0 written on it, and get a sum in a complete of three.
It may be confirmed that 3 is the utmost doable sum.

Constraints:
0 <= numOnes, numZeros, numNegOnes <= 50
0 <= okay <= numOnes + numZeros + numNegOnes

Educating Children Programming – Ok Objects With the Most Sum

We are able to assemble the sorted array, after which choose the Ok objects precisely from the fitting to the left. This has the time complexity of O(N) the place N is the overall quantity (equals to Ones + Zeros + Adverse-Ones). And the area complexity can also be O(N) as we have to put together such an array.

1
2
3
4
5
6

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

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

A particular case is when Ok is zero, we return 0, in any other case we use the checklist comprehension to return the sum of the final Ok numbers of the constructed sorted array (that incorporates numNegOnes -1, numZeros 0, and numOnes 1).

A quicker strategy/algorithm could be to compute those now we have (as we choose them first), then subtract the unfavorable ones which is max(0, k-numZeros-numOnes). If okay is exceeding the quantity of zeros plus ones, then now we have to minus the quantity of unfavorable ones. The time/area complexity is O(1) fixed.

1
2
3

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

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

–EOF (The Final Computing & Know-how Weblog) —

GD Star Ranking
loading…

545 phrases
Final Put up: Introduction to Ledger Digital Crypto Card
Subsequent Put up: Educating Children Programming – Distinct Prime Components of Product of Array