Solution 3 for Scaler Topics Fortnightly Contest - 28
Height of wall
This article is part of the Scaler Topics Fortnightly Contest - 28
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
We will employ binary search to find the optimal answer.
The lower bound can be set to 0, while max(A1,…,An) + B serves as a clear upper bound.
Let b be a resulting array after performing a maximum of B operations.
Suppose for some x we wish to check if we can achieve max(b1,…,bn) ≥ x in at most B operations.
This implies that there must exist some index i such that bi ≥ x. To validate this, we iterate over i from 1 to n and check if it is possible to have bi ≥ x in at most B operations.
Let f(i, y) be the minimum number of operations needed to make bi ≥ y. The following rules apply:
f(i, y) = 0 for all y ≤ Ai,
f(i, y) = y − ai + f(i+1, y−1) for all 1 ≤ i < n and y > Ai,
f(i, y) = +∞ for i = n and all y > Ai.
It’s evident that calculating f(i, x) takes O(n) time for one call in the worst case.
Therefore, our check involves comparing f(i, x) and k for all i from 1 to n. If at least one of the values is ≤ B, it is possible to have some bi ≥ x in at most B operations, and we increase the lower bound in the binary search after updating the current answer. Otherwise, it is impossible, and we decrease the upper bound.
Complexity: O(n^2^⋅logc), where c is the maximum possible value of Ai and B.
Notes:
A solution with O(n^2^⋅logn) complexity is achievable by setting the lower bound in the binary search to max(A1,…,An) and the upper bound to max(A1,…,An) + n.
There exists an O(n^2^) dp solution based on the fact that the answer lies in the range [max(A1,…,An); max(A1,…,An) + n].
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
