Can you please elaborate the algorithm you have used to solve Chefina and Swap’s question?
(Because different people have different ideas or algorithms).
I have used a very simple and intuitive idea. We start by maintaining frequency map of all the elements, if any element has odd frequency then the answer is -1.
Now, we start analysing the main solution. We start by finding all the elements in both the arrays that have to be transferred or swapped. There are many ways to do so but I have done it using two maps to maintain the frequency of all the elements in the respective arrays and then comparing it with the frequency in a another map which has the count of all the elements in both the arrays. Once, we have the list of all the elements that should be transferred from array1 to array2 (and vice versa), the task is pretty simple.
We just sort these lists, one in ascending order and the other one in descending order and pair the corresponding elements together. But is that the most optimal way to swap?
A Keen Observation: Consider an example:
Array1 : 1 1 2 3 3 3 4
Array2 : 1 1 2 3 4 4 4
As, we can observe that we need to swap 1 three and 1 four from array1 and array2 respectively. Now, according to our logic above, we would spend min(3, 4) → 3 for this operation.
However, if we select the minimum element, i.e 1 from array2 and then first swap the element 3 from array1 then the intermediate stage would be:
Array1 : 1 1 2 3 3 1 4
Array2 : 1 3 2 3 4 4 4
Now, we select 1 from array1 and swap 4 from array2 using that 1 and our work is done.
The cost for these 2 operations is 1+1 = 2 which is less than what we spent earlier.
Take away: We need to minimise the cost and the not the number of operations and hence we must always compare if making 2 swaps with the minimums will be cheaper than the minimum element in the current swap.
Here is a link to my submission:
CodeChef: Practical coding for everyone
1 Like