FastPrep
Problem · Array

Permutation Sorter

Learn this problem
● MediumAmazon logoAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

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.

Function

findMinimumOperations(arr: int[]) → int

Examples

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