Solution 2 for Scaler Topics Fortnightly Contest - 22
FREE
Distribution of Gifts Complete Solution
This article is part of the Scaler Topics Fortnightly Contest - 22
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreSolution Approach
One possible approach to solve this problem is to first sort the array A in ascending order since the order of A[i] does not matter for our purpose of comparing the differences. Then we can define a range of possible values for the minimum maximum difference, which will be between left = 0 and right = A[N - 1] - A[0], where N is the length of the array.
To find the optimal minimum maximum difference, we can use binary search. In each iteration of the binary search, we assume the mid value as the current minimum maximum difference, and then we check if it is possible to form B pairs of gifts with differences less than or equal to mid.
=To do this, we can take pairs (A[i], A[i - 1]) greedily if A[i] - A[i - 1] <= mid. If we take this pair, we move to the next available pair (A[i + 2], A[i + 1]). If not, we move to the next available pair (A[i + 1], A[i]). We repeat this process until we have either formed B pairs or we run out of pairs to check.
At the end of each iteration, we check if we have formed B pairs or not. If we have formed B pairs, it means that the current mid value is a valid minimum maximum difference, so we update the right boundary to mid. If we have not formed B pairs, it means that the current mid value is too small, so we update the left boundary to mid + 1.
Once the binary search is complete, we return the left boundary as the optimal minimum maximum difference.
This approach ensures that we find the smallest possible value for the minimum maximum difference that allows us to form B pairs.
Time Complexity: O(N * log(max(A)) + N * logN) Space Complexity: O(logN)
C++ Implementation
Java Implementation
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
