FastPrepFastPrep
Problem Brief

Can Sort Permutation in Given Moves

FULLTIMEOA
See Amazon online assessment and hiring insights

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.

1Example 1

Input
p = [2, 3, 1, 4], moves = [2, 3]
Output
"10"
Explanation

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".

2Example 2

Input
p = [4, 5, 1, 3, 2], moves = [1, 2, 3]
Output
"011"
Explanation

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

Limits and guarantees your solution can rely on.

  • 1 <= n <= 10^5
  • 1 <= q <= 10^5
  • 1 <= moves[i] <= 10^9
  • It is guaranteed that p forms a permutation.
public String canSortPermutation(int[] p, int[] moves) {
  // write your code here
}
Input

p

[2, 3, 1, 4]

moves

[2, 3]

Output

"10"

Sign in to submit your solution.