The goal of the function is to find and print the minimum number of swaps (bribes) in what was initially a sorted array of ints - https://www.hackerrank.com/challenges/new-year-chaos/problem
I have passed this problem with the following code:
def minimumBribes(q): bribeCount = 0 simulated = list(range(1, len(q) + 1)) for i in range(0, len(q)): if q[i] > i+3: print("Too chaotic") return for i in range(0, len(simulated)): if simulated[i] == q[i]: continue while(simulated[i] != q[i]): # do 2 bribes if i + 3 == q[i]: simulated[i + 2], simulated[i + 1] = simulated[i + 1], simulated[i + 2] simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1] bribeCount += 2 # do 1 bribe else: simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1] bribeCount += 1 print(bribeCount)
My approach was to first scan through the array to determine whether it is valid, as 1 person can only bribe (swap) twice, hence the first for loop.
Then I go through each entry in my initial state array(
simulated) and do swaps until the simulated entry at position
i matches that in the final array at the same position.
I'm wondering if there is a better way to do this or whether something can be improved in my approach? I rarely do while loops like this as it seems it could go infinite, but I guess it's okay for this problem as we know only 2 swaps are possible for any entry.