Solution 3 for Scaler Topics Fortnightly Contest - 21
Learn via video course

DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Minimum Product Complete Solution
This article is part of the [Scaler Topics Fortnightly Contest - 21]
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 moreNSDC Certified
Modern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
+1000 moreNSDC Certified
Advanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
+1000 moreNSDC Certified
DevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
+1000 moreNSDC Certified
AI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
3 MonthsDuration
AI-LedCurriculum
Career SupportSupport
NSDC Certified
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
+1000 moreSolution Approach
We are only concerned of frequency of four smallest numbers of the array. There are multiple cases: Let's discuss them one by one -
- Case 1 - If frequency of smallest element is greater than 3. We have to select all four indices of this number. So, if frequency of smallest number is x. Answer would be xC4
- Case 2 - If sum of frequency of smallest two numbers is greater than 3. Let frequency of smallest element is y and the frequency of second smallest element is x. Case a: y = 3 We have to select only 1 index of all second smallest element index. So, answer would be x. Case b: y = 2. We have to select 2 indices of all second smallest element index. So, answer would be xC2. Case c: y = 1. We have to select 3 indices of all second smallest element. So, answer would be xC3.
- Case 3 - If sum of frequency of smallest three numbers is greater than 3. Let the frequency of third smallest element is x. Case a: If the frequency of smallest or second smallest element is 2. In this case frequency sum of smallest two elements is 3. So, we have to select only 1 index of all third smallest element index. So, answer would be x. Case b: If the frequency of smallest and second smallest element is 1 In this case we have to select 2 indices of all third smallest element index. So, answer for this case would be xC2.
- Case 4 - If the frequency of smallest three elements is 1. Let the frequency of fourth smallest element is x. So, we have to select only 1 index of all fourth smallest element index. So, answer for this case would be x.
- So, we can sort the array A and store the frequency of all elements in HashMap.
- And, then find the answer according to the case satisfied.
Time Complexity - O(|A|*log(|A|)) Space Complexity - O(|A|)
C++ Implementation
Sharpen Your Fundamentals with Free Learning
Java Implementation
How Scaler Transformed Careers in Different Fields
₹23L
AVG CTC
SCALER PLACEMENT PROOF
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
11,000+placements
650+companies
Verified data
See full placement report
Hiring Partners:
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more