FastPrep
Problem · Array

Permutation Sorter

● MediumAmazonNEW GRADOA
See Amazon hiring insights

Amazon engineers are testing a new tool, the Permutation Sorter, built to reorder sequences using limited operations.

Given a permutation of integers, the objective is to sort the permutation using only two specific operations:

  1. Reverse the entire permutation.
  2. Transfer the first element of the permutation to the last position, i.e., change arr[0], arr[1], ..., arr[n-1] to arr[1], arr[2], ..., arr[n-1], arr[0].

Formally, given a permutation arr of size n, determine the minimum number of operations needed to sort the given permutation in increasing order. The permutation provided is guaranteed to be sorted using only these two operations.

Note: A permutation of length n is a sequence of integers from 1 to n containing each number exactly once.

Complete the function findMinimumOperations in the editor below.

Examples
01 · Example 1
arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
return = 3

For n = 10, the permutation can be sorted by performing the following operations:

  1. Reverse the permutation to get arr = [1, 10, 9, 8, 7, 6, 5, 4, 3, 2].
  2. Transfer the first element to the last position to get arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1].
  3. Reverse the permutation to get arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

It can be shown that the given permutation can only be sorted using a minimum of 3 operations.

More Amazon problems
drafts saved locally
public int findMinimumOperations(int[] arr) {
  // write your code here
}
arr[2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
expected3
checking account