FastPrepCan Sort Permutation in Given Moves
Problem · Math

Can Sort Permutation in Given Moves

Learn this problem
● MediumAmazon logoAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Amazon recently conducted interviews where the candidates were asked to sort the permutation p of length n. Then the ith candidate sorted the permutation in moves[i] moves. To verify the result once more, the interviewer wants to find if it is possible to sort the given permutation in the given number of moves. Given the original permutation array p and the number of moves made by each of the q candidates, find whether you can sort the permutation p by performing exactly moves[i] moves. In one move, you swap the value at any two distinct indexes. Return the answer as a binary string of length q. The value at the ith index should be 1 if it is possible to sort the permutation in exactly moves[i] moves, otherwise the value should be 0.

Note: A permutation is a sequence of n distinct integers such that each integer between [1, n] appears exactly once. For example, [1, 2, 3, 4] is a permutation of size 4, but [1, 3, 4, 5] or [1, 2, 2, 4] is not.

Function

canSortPermutation(p: int[], moves: int[]) → String

Examples

Example 1

p = [2, 3, 1, 4]moves = [2, 3]return = "10"

For the first candidate with 2 moves:

  1. Swap index 0 and 2 (Permutation becomes [1, 3, 2, 4])
  2. Swap index 1 and 2 (Permutation becomes [1, 2, 3, 4])
The permutation is sorted in exactly 2 moves, so the answer is 1 for the first candidate.

For the second candidate with 3 moves, it is not possible to sort the permutation in exactly 3 moves, so the answer is 0 for the second candidate.

The final answer is "10".

Example 2

p = [4, 5, 1, 3, 2]moves = [1, 2, 3]return = "011"

Outputs from these two examples are educated guesses :)

It is not possible to sort the permutation in exactly 1 move, so the answer is 0 for the first candidate.

For the second candidate with 2 moves:

  1. Swap index 0 and 4 (Permutation becomes [2, 5, 1, 3, 4])
  2. Swap index 1 and 2 (Permutation becomes [2, 1, 5, 3, 4])
The permutation is not sorted, so the answer is 0 for the second candidate.

For the third candidate with 3 moves, it is possible to sort the permutation, so the answer is 1 for the third candidate.

The final answer is "011".

Constraints

  • 1 <= n <= 10^5
  • 1 <= q <= 10^5
  • 1 <= moves[i] <= 10^9
  • It is guaranteed that p forms a permutation.

More Amazon problems

drafts saved locally
public String canSortPermutation(int[] p, int[] moves) {
  // write your code here
}
p[2, 3, 1, 4]
moves[2, 3]
expected"10"
checking account