Last Updated: 29 Dec, 2021
The Twin Houses
Easy
Asked in company
There are 'N' houses on the left side of the road and 'N' houses on the right side. All of these houses are coloured. The colour of houses on the left and right sides is given by arrays 'A' and 'B', respectively.
Both the arrays 'A' and 'B' are permutations of length 'N'. A permutation of length 'N' is the sequence of length 'N', which consists of all the integers from 1 to 'N' exactly once.
For an 'i-th' house on the left side, you are supposed to find the house on the right side with the same colour as 'A[i]'.
Example :
'N' = 3, 'A' = {1, 2, 3}, 'B' = {2, 3, 1}.
House 1 on the left side has the same colour as house 3 on the right side.
House 2 on the left side has the same colour as house 1 on the right side.
House 3 on the left side has the same colour as house 2 on the right side.
The answer is {3, 1, 2}.
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains an integer 'N', denoting the number of houses.
The second line contains 'N' space-separated integers denoting the colour of the houses on the left side.
The third line contains 'N' space-separated integers denoting the colour of the houses on the right side.
Output format :
For each test case, print 'N' space-separated integers denoting the position of the house on the right side with the same colour as 'i-th' house on the left side.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i], B[i] <= N
All the values in 'A' and 'B' are unique.
Sum of 'N' over all test cases is <= 10^5.
Time Limit: 1 sec
Approaches
Approach :
- Traverse through the house on the left side.
- For each house on the left side, find the house of the same colour by iterating through all the houses on the right side.
Algorithm:
- Initialise an array 'POSITION' of length 'N' with 0.
- Loop through the array 'A' from 'i' = 1 to 'i' = 'N' :
- Loop through the array 'B' from 'j' = 1 to 'j' = 'N' :
- If 'A[i]' is equal to 'B[j]' :
- 'POSITION[i]' = 'j'
- Continue to outer loop
- If 'A[i]' is equal to 'B[j]' :
- Loop through the array 'B' from 'j' = 1 to 'j' = 'N' :
- Return 'POSITION'.
Approach :
- First, we will map the house's colour on the right to its position. For example 'B' = {3, 1, 4, 2}. The mapping will be :
- House with colour 1 is at position 3.
- House with colour 2 is at position 4.
- House with colour 3 is at position 1.
- House with colour 4 is at position 2.
- For every house on the left, we can easily find the position of the house on the right using this mapping.
Algorithm:
- Initialise an array 'COLORPOSRIGHT' of length 'N' as 0.
- Initialise an array 'POSITION' of length 'N' as 0.
- Loop through houses on the right from 'i' = 1 to 'i' = 'N' :
- Initialise a variable 'X' as 'B[i]'.
- 'COLORPOSRIGHT'[X]' = i
- Loop through houses on the left from 'i' = 1 to 'i' = 'N' :
- Initialise a variable 'X' as 'A[i]'.
- 'POSITION[i]' = 'COLORPOSRIGHT'[X]'
- Return 'POSITION'.
Similar problems