FastPrep
Problem · Math

Sort Permutation

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Amazon recently conducted interviews where the candidates were asked to sort the permutation p of length n. The ith candidate sorted the permutation in moves[i] moves. To verify the results once more, the interviewers want to find if it is possible to sort the 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 can swap values at any two distinct indices. 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 p in exactly moves[i] moves, or 0 otherwise.

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

Function

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

Complete the function sortPermutation in the editor.

sortPermutation has the following parameters:

  1. 1. int[] p: the original permutation array
  2. 2. int[] moves: the number of moves made by each candidate

Returns

String: a binary string of length q where each character is either '1' or '0'

𓇼 ⋆.˚𓆝Credit to niketpatel3 𓆡⋆.˚𓇼

Examples

Example 1

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

- In the first query, moves[0] = 2, We can sort the given permutation in exactly 2 moves,

  • Swap 0th and 2nd index, p = [1,3,2,4]
  • Swap 1st and 2nd index, p = [1,2,3,4]

- In the second query, moves[1] = 3, It can be shown that It is not possible to sort the given permutation in exactly 3 moves.

The answer is the string "10".

Constraints

🌧️

More Amazon problems

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