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.
- New Year Chaos
- Discussions
New Year Chaos
New Year Chaos
Sort by
recency
|
67 Discussions
|
Please Login in order to post a comment
Java
Python 3
Reply to https://www.hackerrank.com/challenges/one-month-preparation-kit-new-year-chaos/forum/comments/1083532
1 2 3 4 5 6 7 8
Bribe/Swap 4 to its position 1 2 3 5 6 7 8 4: [(4,5), (4,6), (4,7), (4,8)]
Swap 6 to its position 1 2 3 5 7 8 6 4: [(6, 7), (6, 8)]
Swap 3 and 5 1 2 5 3 7 8 6 4 [(3, 5)]
I suspect that you were trying to do something like
bribe=sum(abs(q[i] - 1 - i))
. Notice that when we swap 6 to its position we increasedbribe
by 1 even though 2 swaps were required.Here's a simpler test case: 2 4 3 1
The key observation is the person cannot bribe and move ahead more than two spots.
At position
i
, the person originally at this spot (with valuei+1
) can now be at index [i-2, n-1] inclusive. The person can only be ahead at most two spot, but can be behind without limit. This observation forces us to iterate in the reverse order.The idea behind the implementation is to swap the values to undo the bribes so that the array is sorted. This is somewhat like a bubble sort, but remember that we will iterate in reverse order and only have to swap from
i
toi-2
. The runtime is therefore O(N*2) = O(N)I'm optimizing the code for readability and understandability. You may be able to optimize this so that you don't have to do the swaping.
Kotlin: