Apple Redistribution into Boxes

Easy
995.

Apple Redistribution into Boxes

Apple Redistribution into Boxes is an easy coding problem on arrays, sorting and greedy, asked in Amazon, Google and Cognizant interviews.

apple[i] apples are packed in the i-th pack, and capacity[j] is how many apples box j holds. A pack's apples may be split across boxes.

Return the minimum number of boxes needed to hold every apple. The input always allows a solution.

Example 1

Input
apple = [1,3,2], capacity = [4,3,1,5,2]
Output
2
Explanation
Six apples fit in the boxes of size 5 and 4.

Example 2

Input
apple = [5,5,5], capacity = [2,4,2,7]
Output
4
Explanation
Fifteen apples need every box.

Example 3

Input
apple = [1], capacity = [10]
Output
1

Constraints

  • 1 <= apple.length <= 50
  • 1 <= capacity.length <= 50
  • 1 <= apple[i], capacity[i] <= 50
  • The input is generated so that it is possible to redistribute the apples.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} apple
 * @param {number[]} capacity
 * @return {number}
 */
var minimumBoxes = function(apple, capacity) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Apple Redistribution into Boxes — Problem & Solution

Apple Redistribution into Boxes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Apple Redistribution into Boxes is an easy coding problem on arrays, sorting and greedy, asked in Amazon, Google and Cognizant interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

apple[i] apples are packed in the i-th pack, and capacity[j] is how many apples box j holds. A pack's apples may be split across boxes.

Return the minimum number of boxes needed to hold every apple. The input always allows a solution.

Example 1

Input: apple = [1,3,2], capacity = [4,3,1,5,2]
Output: 2
Explanation: Six apples fit in the boxes of size 5 and 4.

Example 2

Input: apple = [5,5,5], capacity = [2,4,2,7]
Output: 4
Explanation: Fifteen apples need every box.

Example 3

Input: apple = [1], capacity = [10]
Output: 1

Constraints

  • 1 <= apple.length <= 50
  • 1 <= capacity.length <= 50
  • 1 <= apple[i], capacity[i] <= 50
  • The input is generated so that it is possible to redistribute the apples.

Hints for Apple Redistribution into Boxes

  1. Hint 1

    Because packs can be split, only the total number of apples matters.

  2. Hint 2

    To use as few boxes as possible, fill the largest ones first.

  3. Hint 3

    Sort the capacities descending and take them until the total is covered.

How to solve Apple Redistribution into Boxes

Splitting packs means only the total count matters, so sort the capacities largest-first and take boxes until their combined capacity reaches the total.

Approach

  1. Sum the apples.
  2. Sort capacity descending.
  3. Take boxes in that order, subtracting each capacity, until the remaining total is non-positive.
  4. Return how many boxes were taken.

Why it works

Splitting is what collapses this to a single number: without it, packs would have to be assigned whole and the problem would become bin packing. With it, any set of boxes whose capacities sum to at least the total works, so the greedy largest-first choice is optimal.

Complexity

  • Time — O(m log m)
  • Space — O(m)

Pitfalls

  • Sorting ascending uses more boxes than necessary.
  • The individual pack sizes never matter, only the total.
  • The loop must stop as soon as the total is covered.

Reference solution

Python

from typing import List

def minimumBoxes(apple: List[int], capacity: List[int]) -> int:
    total = sum(apple)
    used = 0
    for c in sorted(capacity, reverse=True):
        if total <= 0:
            break
        total -= c
        used += 1
    return used

Java

public static int minimumBoxes(int[] apple, int[] capacity) {
    int total = 0;
    for (int v : apple) total += v;
    Integer[] sorted = new Integer[capacity.length];
    for (int i = 0; i < capacity.length; i++) sorted[i] = capacity[i];
    Arrays.sort(sorted, Comparator.reverseOrder());
    int used = 0;
    for (int c : sorted) {
        if (total <= 0) break;
        total -= c;
        used++;
    }
    return used;
}

C++

int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
    int total = 0;
    for (int v : apple) total += v;
    vector<int> sorted = capacity;
    sort(sorted.begin(), sorted.end(), greater<int>());
    int used = 0;
    for (int c : sorted) {
        if (total <= 0) break;
        total -= c;
        used++;
    }
    return used;
}

JavaScript

var minimumBoxes = function(apple, capacity) {
    var total = 0, i;
    for (i = 0; i < apple.length; i++) total += apple[i];
    var sorted = capacity.slice();
    sorted.sort(function(a, b) { return b - a; });
    var used = 0;
    for (i = 0; i < sorted.length; i++) {
        if (total <= 0) break;
        total -= sorted[i];
        used++;
    }
    return used;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms