Mario's Divisibility Dilemma

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

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

Let’s consider the scenario where there exists a value ‘k’ that evenly divides the number of chocolates in each box. In this case, ‘k’ must be a divisor of the total sum of chocolates across all boxes.
To ensure that the number of chocolates in each box is divisible by ‘k’, we have two options: either the chocolates in each box should be exactly ‘k’, or they should be ‘0’. However, any other multiple of ‘k,’ like 2k or 3k, would necessitate more moves, as you can deduce.
To minimize the number of moves required, we would redistribute the chocolates in a way that the first ‘k’ boxes containing 1 chocolate consolidate all these chocolates into the box at their median position. It is straightforward to demonstrate that this is the optimal strategy. This process is repeated (sum / k) times.
By applying this strategy, we can systematically evaluate each divisor of the total chocolate sum and calculate the number of moves required to achieve the desired distribution. The divisor that results in the fewest moves will be our answer.

Time Complexity: $O(N * sqrt(N))$