How should I practice Get Minimum Operations to Sort Array?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Moveworks online assessment problems in FastPrep.

Is Get Minimum Operations to Sort Array associated with Moveworks?

FastPrep tags this as a Moveworks coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Get Minimum Operations to Sort Array

Learn this problem

● HardMoveworksFULLTIMEINTERNOA

Problem statement

You are given an unsorted positive-integer array arr of length n. You may perform the following operation any number of times:

Select an element arr[i] and replace it with two positive integers a and b such that a + b = arr[i].

Return the minimum number of operations required to make the resulting array non-decreasing.

Function

getMinimumOperationsToSortArray(arr: int[], n: int) → long

Examples

Example 1

arr = [3, 4, 3]n = 3return = 2

Split 4 into 2, 2, producing [3, 2, 2, 3]. Then split 3 into 1, 2, producing the non-decreasing array [1, 2, 2, 2, 3]. This uses two operations.

Constraints

1 <= n <= 10^5
1 <= arr[i] <= 10^9