Solution 3 for Scaler Topics Fortnightly Contest - 4

This article is part of the Scaler Topics Fortnightly Contest - 4.

Transform Your Career

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

Solution Approach

• If you were working in real life what strategy you would have followed?
• You would have been greedy while carrying the plates.
• If you are at sink i, can you calculate how many plates would cross sink i?
• Let’s say finally ‘avg’ number of plates will be present in each sink When you are at sink i, if sum of plates till index ‘i’ is more than ‘avgi’ plates, then definitely those extra plates would go beyond and though the index i. That means at some point we will make ‘sum[1…i] - avgi’ moves.
• Similarly if sum[1…i] is less than ‘avgi’ plates, we will need ‘avgi - sum[1..i]’ plates, crossing index i.
• Therefore the answer is sum of abs(sum[1…i] - avg*i) for all the index.If you were working in real life what strategy you would have followed?
• You would have been greedy while carrying the plates. If you are at sink i, can you calculate how many plates would cross sink i?
• Let’s say finally ‘avg’ number of plates will be present in each sink. When you are at sink i, if sum of plates till index ‘i’ is more than ‘avgi’ plates, then definitely those extra plates would go beyond and though the index i. That means at some point we will make ‘sum[1…i] - avgi’ moves.
• Similarly if sum[1…i] is less than ‘avgi’ plates, we will need ‘avgi - sum[1..i]’ plates, crossing index i.
• Therefore the answer is sum of abs(sum[1…i] - avg*i) for all the index.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation