Solution 3 for Scaler Topics Fortnightly Contest - 8

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

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

• We use Binary Search to solve this problem.

• To check if X number of groups can be made, we see that we require a total of X*B students (where B is the minimum size of the group).

• Let it be reqStudents.

• We can loop over the sections and take $min(A[i], X * C)$ students from that section.

• If its sum is greater than or equal to reqStudents, then it is possible to make X number of groups.

• Hence, we take l = 0, r = totalNumberOfStudents and $mid = (l + r)/2$.

• If it is possible to make mid number of groups we make $l = mid+1$, else $r = mid-1$.

• We will keep doing the same while $l <= r$.

Time Complexity:- $O(N*Log(ΣA[i]))$

Total Space Complexity:- O(1)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation