Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1196.html

1196. How Many Apples Can You Put into the Basket

Level

Easy

Description

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.

Example 1:

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.

Example 2:

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.

Constraints:

  • 1 <= arr.length <= 10^3
  • 1 <= arr[i] <= 10^3

Solution

To put most apples in the basket, always select the apples with the least weight. Simply sort the array and select the apples from the least weight to the most weight until total weight exceeds the upper bound. The last apple makes total weight exceed the upper bound, so remove it. Return the number of apples at this point.

The reason why selecting the apples with the least weight works is that after the apples with the least weight are selected, changing any apple with another apple will definitely increase the total weight of apples selected (except the newly selected apple has the same weight as the previously selected apple), so it is possible that the total weight exceeds the upper bound, but the number of apples selected will never increase. So always select the apples with the least weight.

  • class Solution {
    public int maxNumberOfApples(int[] arr) {
        Arrays.sort(arr);
        int length = arr.length;
        final int CAPACITY = 5000;
        int totalWeight = 0;
        int count = 0;
        for (int i = 0; i < length; i++) {
            int weight = arr[i];
            if (totalWeight + weight <= CAPACITY) {
                totalWeight += weight;
                count++;
            } else
                break;
        }
        return count;
    }
}

  • // OJ: https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maxNumberOfApples(vector<int>& A) {
        sort(begin(A), end(A));
        int sum = 0, i = 0, N = A.size();
        while (i < N && sum + A[i] <= 5000) sum += A[i++];
        return i;
    }
};

  • class Solution:
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        ans = 0
        t = 0
        for v in weight:
            if t + v > 5000:
                break
            t += v
            ans += 1
        return ans



  • func maxNumberOfApples(weight []int) int {
	sort.Ints(weight)
	ans, t := 0, 0
	for _, v := range weight {
		if t+v > 5000 {
			break
		}
		t += v
		ans++
	}
	return ans
}

  • function maxNumberOfApples(weight: number[]): number {
    weight.sort((a, b) => a - b);
    let s = 0;
    for (let i = 0; i < weight.length; ++i) {
        s += weight[i];
        if (s > 5000) {
            return i;
        }
    }
    return weight.length;
}

All Problems

All Solutions