recategorized by
4,800 views
26 votes
26 votes

Consider an array $A[1...n]$. It consists of a permutation of numbers $1....n$. Now compute another array $B[1...n]$ as follows: $B[A[i]]:= i$ for all $i$. Which of the following is true?

  1. $B$ will be a sorted array.
  2. $B$ is a permutation of array $A$.
  3. Doing the same transformation twice will not give the same array.
  4. $B$ is not a permutation of array $A$.
  5. None of the above.
recategorized by

5 Answers

Best answer
38 votes
38 votes

Option (b) B is a permutation of array A.

In fact, $B$ gives the reverse index of all the elements of array $A$. Since the array $A$ contains numbers $[1 .. n]$ mapped to the locations $[1 .. n]$ and $A$ is a permutation of the numbers $[1 .. n]$, the array $B$ will also be a permutation of the numbers $[1 .. n]$.

For example: $$\begin{array}{l|cccccccc} \text{index} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\[1em] \hline A & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4\\ B & 2 & 6 & 3 & 8 & 1 & 5 & 4 & 7 \end{array}$$


To see that option c is incorrect, let array $C$ be the array attained from doing the same transformation twice, that is, $C[B[i]] = i , \forall i \in [1 .. n]$. We get, $$\begin{array}{l|cccccccc} \text{index} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\[1em] \hline A & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4\\ B & 2 & 6 & 3 & 8 & 1 & 5 & 4 & 7\\ C & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4 \end{array}$$

We can see that $C = A$, which makes option c incorrect.

edited by
2 votes
2 votes

let n=2
A[1,2] and it consists of a permutation of numbers 1,2 which are 
case 1: (1,2)
case 2: (2,1)
B[A[i]]:=i  for all i (GIVEN)
case 1: B[A[1]]:=1 B[1]:=1
             B[A[2]]:=2 B[2]:=2 so B=(1,2)
case 2: B[A[1]]:=1 B[2]:=1
             B[A[2]]:=2 B[1]:=2 so B=(2,1)
Hence array B have permutation of 1,2

Ans is B


 

2 votes
2 votes

Let n=4 ,so indexes from 1 to 4.

Ex 1 - A[3,2,1,4] then B is B[3,2,1,4]

Ex 2 - A[4,2,1,3] then B is B[3,2,4,1]

From the examples above

Option C - Doing the same transformation twice will not give the same array. is proven false by Ex 1. As A=B.

Option A - B will be a sorted array. is proven false by Ex 2.

Option B - B is a permutation of array A.

From google - meaning of permutation - "each of several possible ways in which a set or number of things can be ordered or arranged.". As we see both Ex 1 and Ex 2 B's are permutations of their A's.

Option D - is false if option B is True.

So Answer is option B.

1 votes
1 votes
Given that array is start from 1 to n

let assume A[i] = x; therefore where can be this x in sorted array ? it is at xth position

B[x]=x but we are getting B[x]=i ===> option A is wrong

Note that A[i] given different results because of no repetition of numbers.. that implies every index of B is accessed and moreover we fill the index of B with i which is different ===> B contains the permutation order of A
Answer:

Related questions