Chocolate Boxes Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 18

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

If there are x boxes allocated for a specific chocolate type it is optimal to distribute the chocolates evenly in these boxes. So the max chocolate in a box will be ceil(A[i] / x).
Try to think greedily. First assign 1 box to each chocolate type.
Now try to think which type of chocolate should get one new box and come up with an algorithm.
Create a sorted set of the chocolate types with respect to the maximum number of chocolates in the allocated boxes.
Initially assign one box to each type. Now for each of the remaining boxes assign it to type with most number of chocolates in a box. Finally after allocating all the boxes the box with most chocolates is the answer.
Check implementation for deatils.

Time Complexity - O(B log N). As for every box we do operations on the set which works in log N time. Space Complexity - O(N)