Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Apple Redistribution into Boxes (easy)

Problem Statement

You are given an array apple of size n, where the apple[i] represents the number of apples in i<sup>th</sup> pack. You are also given an array capacity of size m, where capacity[j] is a number of apples that can be stored in the j<sup>th</sup> box.

Return the minimum number of boxes you need to use to put these all n packs of apples into boxes.

Note: You are allowed to distribute apples from the same pack into different boxes.

Examples

Example 1:

  • Input: apple = [2, 3, 1], capacity = [4, 2, 5, 1]
  • Expected Output: 2

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jimmy

· 2 years ago

When submitting my code, it fails on this particular test case:

[]

[1, 2, 3]

The constraints state:

1 <= n == apple.length <= 50

1 <= m == capacity.length <= 50

1 <= apple[i], capacity[i] <= 50

The apples array shouldn't be empty so this shouldn't be a valid test case.

Show 1 reply
amit.x.sethi

amit.x.sethi

· 2 years ago

a bit confusing... The problem description says that we can not split the apples from the same pack into different boxes, but the examples mention taking apples from a pack partially.

Show 1 reply
Em Eff

Em Eff

· a year ago

Input:

[2, 3, 1]
[4]

According to the constraints for this problem:

The input is generated such that it's possible to redistribute packs of apples into boxes.

In the above case, there's a single box with a capacity of 4, yet there are 6 apples. I think that either the test case should be updated, or that the constraint should be clarified to mention that not all apples need to be in boxes.

My initial logic was incrementing the box count by 1 if "the current box is empty and there are apples remaining," under the assumption there would always be room for the remaining apples.