Apple Redistribution into Boxes - Practice Coding Problems

Apple Redistribution into Boxes - Problem

You are given an array apple of size n and an array capacity of size m. There are n packs where the i^th pack contains apple[i] apples. There are m boxes as well, and the i^th box has a capacity of capacity[i] apples.

Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes. Note that, apples from the same pack can be distributed into different boxes.

Input & Output

Example 1 — Basic Case

$ Input: apple = [1,3,2], capacity = [4,3,1,5,2]

› Output: 2

💡 Note: We need 1+3+2 = 6 apples total. Using boxes with capacity [5,4] gives us 9 capacity, which is enough. We need minimum 2 boxes.

Example 2 — Single Large Box

$ Input: apple = [5,5,5], capacity = [2,4,2,7]

› Output: 4

💡 Note: Total apples = 15. Even the largest box (7) isn't enough alone. We need all boxes: 2+4+2+7 = 15.

Example 3 — Perfect Fit

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

› Output: 1

💡 Note: Total apples = 5. Single box with capacity 10 is more than enough.

Constraints

1 ≤ n, m ≤ 50
1 ≤ apple[i] ≤ 50
1 ≤ capacity[i] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Apple packs [1,3,2] and box capacities [4,3,1,5,2]

Process

Sum apples (6), sort boxes [5,4,3,2,1], pick largest until sum ≥ 6

Output

Minimum 2 boxes needed (capacity 5+4=9 ≥ 6 apples)

Key Takeaway

🎯 Key Insight: Greedy algorithm works because using larger boxes first always leads to the minimum number of boxes needed.

Asked in

🍎 Apple 15 G Google 12 a Amazon 8

The key insight is to use a greedy approach: sort boxes by capacity in descending order and keep selecting the largest boxes until we have enough total capacity for all apples. Best approach is Greedy Algorithm with Time: O(n + m log m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Largest Boxes First	O(n + m log m)	O(1)	Sort boxes by capacity descending, then pick largest boxes until we have enough space
Brute Force - Try All Combinations	O(2^m)	O(1)	Generate all possible subsets of boxes and find minimum that fits all apples

Greedy - Largest Boxes First — Algorithm Steps

Calculate total apples across all packs
Sort boxes by capacity in descending order
Keep adding largest available boxes until capacity >= total apples
Return count of boxes used

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total

Sum apples: 1+3+2 = 6

Sort Descending

Sort boxes: [6, 5, 4]

Pick Greedily

Take box 6: capacity=6 >= 6 apples, so we need 1 box

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a); // Descending order
}

int solution(int* apple, int appleSize, int* capacity, int capacitySize) {
    int totalApples = 0;
    for (int i = 0; i < appleSize; i++) {
        totalApples += apple[i];
    }
    
    qsort(capacity, capacitySize, sizeof(int), compare);
    
    int boxesUsed = 0;
    int currentCapacity = 0;
    
    for (int i = 0; i < capacitySize; i++) {
        boxesUsed++;
        currentCapacity += capacity[i];
        if (currentCapacity >= totalApples) {
            break;
        }
    }
    
    return boxesUsed;
}

int main() {
    char line[1000];
    int apple[50], capacity[50];
    int appleSize = 0, capacitySize = 0;
    
    // Parse apple array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            apple[appleSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse capacity array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            capacity[capacitySize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(apple, appleSize, capacity, capacitySize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m log m)

O(n) to sum apples + O(m log m) to sort capacity + O(m) to select boxes

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for sum, count, and in-place sorting

✓ Linear Space

24.6K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Largest Boxes First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler