We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
In this problem, my intuition was telling me to just count the different positions between the input array and the sorted input array and then divide this count between 2 rounding up. For example:
input array: 1 5 3 4
sorted array: 1 3 4 5
count: 0 1 1 1 = 3
number of swaps = ceil(3/2) = 2
In all the cases that I have tried I get the correct answer. I take into account normal and reverse order. However, test cases #1,#2,#3,#6 give me a wrong answer. Could someone tell me the problem in my reasoning or give me a counter example?
The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
In this problem, my intuition was telling me to just count the different positions between the input array and the sorted input array and then divide this count between 2 rounding up. For example: input array: 1 5 3 4 sorted array: 1 3 4 5 count: 0 1 1 1 = 3 number of swaps = ceil(3/2) = 2
In all the cases that I have tried I get the correct answer. I take into account normal and reverse order. However, test cases #1,#2,#3,#6 give me a wrong answer. Could someone tell me the problem in my reasoning or give me a counter example?
Hey, counter example here:
the expected output is 3, but with your logic:
the output is ceil(4/2) = 2
The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.
reply guys