Minimum Operations to Convert Array
Nutanix● MediumOAProblem statement
Given an array arr of length n, the following types of operations can be performed on it:
- Operation type 1: Shift the array cyclically by 1 towards the left.
- Operation type 2: Swap any 2 elements of the array.
However, once an operation of type 2 is performed, operations of type 1 cannot be performed again. The participants are required to find the minimum number of operations in which the given array can be converted into the sequence (1, 2, 3, ..., n).
Note: It is guaranteed that the array arr is a permutation of the target array [1, 2, 3, ..., n] and hence, the answer will always exist.
Function
minimumOperationsToConvertArray(arr: int[]) → int
Complete the function minimumOperationsToConvertArray in the editor.
minimumOperationsToConvertArray has the following parameter:
int[] arr: an array of integers
Returns
int: the minimum number of operations required
Examples
Example 1
arr = [5, 3, 2, 1, 4]return = 2The following sequence of operations can be performed:
- Type 1: Shift the array cyclically left once to obtain
(3, 2, 1, 4, 5). - Type 2: Swap the first and third elements, the array becomes
(1, 2, 3, 4, 5)which is the required target.
It can be shown that the array cannot be transformed in less than 2 operations. Thus, the answer is 2.