You have some apples, where
arr[i] is the weight of the
i-th apple. You also have a basket that can carry up to
5000 units of weight.
Return the maximum number of apples you can put in the basket.
Input: arr = [100,200,150,1000] Output: 4 Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.
Input: arr = [900,950,800,1000,700,800] Output: 5 Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.
1 <= arr.length <= 10^3
1 <= arr[i] <= 10^3
Sort apple weights in ascending order then check at where the weight sum is higher than the threshold.
class Solution: def maxNumberOfApples(self, arr: List[int]) -> int: arr = sorted(arr) maximum = 0 sum_weight = 0 for i, apple in enumerate(arr): sum_weight += apple if sum_weight > 5000: break maximum = i + 1 return maximum
- Time Complexity: O(Nlog(N)).
- Space Complexity: O(1).