FastPrep

Description

Solutions

Can Sort Permutation in Given Moves

🔥 FULLTIME📚RELATED PROBLEMS

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.

Example 1:

Input:  p = [2, 3, 1, 4], moves = [2, 3]
Output: "10" 
Explanation:
      
        For the first candidate with 2 moves:
        

          Swap index 0 and 2 (Permutation becomes [1, 3, 2, 4])
          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:

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:
        

          Swap index 0 and 4 (Permutation becomes [2, 5, 1, 3, 4])
          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.