FastPrepMinimum Replacements to Sort the Array
Problems/Minimum Replacements to Sort the Array

Minimum Replacements to Sort the Array

Rubrik logoRubrik● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was the second of four questions in a 75-minute Rubrik online assessment for a CPD intern role. The post links the public problem Minimum Replacements to Sort the Array and says every test passed.

The post adds no limits or examples, so this version keeps the usual ones: up to 10^5 numbers, each from 1 to 10^9.

Our version is about 95% the same as the reported question.

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[]) → long

Examples

Example 1

nums = [12,5]return = 2

12 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 = 0

The array is already sorted, so no operation is needed.

Example 3

nums = [5,7,2]return = 7

The 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^5
  • 1 <= 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
All Rubrik interview questionsSee Rubrik hiring insights
Saved
class Solution {
    public long minimumReplacement(int[] nums) {
        // Write your code here.
    }
}
Checking account…