Minimum Replacements to Sort the Array
Updated
Problem statement
You are given an integer array nums. In one operation, you may pick any element and replace it with two positive integers whose sum equals that element. The two new elements take its place, in either order.
For example, in [8, 3, 9] you can replace 8 with 3 and 5 to get [3, 5, 3, 9].
Return the minimum number of operations needed to make the array sorted in non-decreasing order.
Function
minimumReplacement(nums: int[]) → longExamples
Example 1
nums = [12,5]return = 212 is bigger than 5, so it must be split into pieces that are each at most 5. Two pieces are not enough because 5 + 5 = 10. Three pieces work, for example 4, 4, 4, which takes 2 operations. The array becomes [4, 4, 4, 5].
Example 2
nums = [1,2,3,4]return = 0The array is already sorted, so no operation is needed.
Example 3
nums = [5,7,2]return = 7The last element 2 is never split. 7 must become pieces of at most 2, which needs at least four pieces, such as 1, 2, 2, 2 (3 operations). Any four or more such pieces include a 1, so 5 must then become pieces of at most 1: five pieces of 1 (4 operations). The total is 3 + 4 = 7.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^9
More Rubrik Online Assessment questions
- Delete and Freeze GameOA · Seen Nov 2026
- Delete K Subsets for Maximum ScoreOA · Seen Nov 2026
- Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
- Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
- Get Minimum OperationsOA · Seen Nov 2024
- Horizontal Pod AutoscalerOA · Seen Nov 2024
- Stock PricesOA · Seen Nov 2024
- StarlightOA · Seen Oct 2024
- Energy CrisisOA · Seen Sep 2024
- Mike and GemsOA · Seen Sep 2024
Similar questions at other companies
- Lock CodeVisa · OAVisa interview questions
- Lock CodeGoldman Sachs · OAGoldman Sachs interview questions
- Find Maximum CaloriesAmazon · OA
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Server InvestmentRippling · OARippling interview questions
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimize Adjacent Squared-Difference Cost with One InsertionMicrosoft · OAMicrosoft interview questions
- Minimum Halvings for Alternating ParityIBM · OAIBM interview questions
- Resource AllocationMaven Securities · OAMaven Securities interview questions