> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/2022/oa/movingboxes.md).

# MovingBoxes

https\://leetcode.com/discuss/interview-question/1733741/Amazon-OA-or-SDE-Intern

You are an amazon delivery and you have some boxes that you have to deliver, but there are some conditions -

* You can take 2 boxes of same weight in one round
* you can take 3 boxes of same weight in one round

You have to find the minimum number of rounds to deliver the boxes or -1 if it is not possible to deliver them.

Example cases -\
**Input:** boxes - \[2, 2, 3, 3, 2, 4, 4, 4, 4, 4]\
**Output:** 4\
**Explanation:** 3 boxes of weight 2 in 1st round, 2 boxes of weight 3 in 2nd round, 3 boxes of wt 4 in 3rd and 2 boxes of wt 4 in 4th round.

**Input:** boxes - \[2, 3, 3]\
**Output:** -1\
**Explanation:** There is only one box with weight 2 and we can only take either 2 or 3 boxes in one round not lesser.

**My Approach:**

* Make a Counter of frequency of weights
* If there is any weight with frequency 1 **return -1**
* otherwise iterate through all frequencies and calculate minimum number of rounds for that frequency.
* this is similar to minimum number of coins to change the particular value where coins are 2 and 3\
  Let **f** is the maximum of frequency of any weight and there are **c** unique weights then\
  **Time Complexity:** O(max(f, c))\
  **Space Complexity:** O(f)
* Minimum number of rounds can be calculated directly in **O(1)** because we can convert all the numbers as a sum of 2 and 3. (this came to my mind after submitting the test, I solved this using coin change method using DP)