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.
No need to swap values, no need to loop backwards, no need to loop more than once. Just loop through each person in the queue and check two things: 1. Has this person moved more than two positions forward?
2. How many times has this person been bribed?
In Python3:
defminimumBribes(Q):## initialize the number of movesmoves=0## decrease Q by 1 to make index-matching more intuitive# so that our values go from 0 to N-1, just like our# indices. (Not necessary but makes it easier to# understand.)Q=[P-1forPinQ]## Loop through each person (P) in the queue (Q)fori,Pinenumerate(Q):# i is the current position of P, while P is the# original position of P.## First check if any P is more than two ahead of # its original positionifP-i>2:print("Too chaotic")return## From here on out, we don't care if P has moved# forwards, it is better to count how many times# P has RECEIVED a bribe, by looking at who is# ahead of P. P's original position is the value# of P.# Anyone who bribed P cannot get to higher than# one position in front if P's original position,# so we need to look from one position in front# of P's original position to one in front of P's# current position, and see how many of those # positions in Q contain a number large than P.# In other words we will look from P-1 to i-1,# which in Python is range(P-1,i-1+1), or simply# range(P-1,i). To make sure we don't try an# index less than zero, replace P-1 with# max(P-1,0)forjinrange(max(P-1,0),i):ifQ[j]>P:moves+=1print(moves)
New Year Chaos
You are viewing a single comment's thread. Return to all comments →
No need to swap values, no need to loop backwards, no need to loop more than once. Just loop through each person in the queue and check two things: 1. Has this person moved more than two positions forward? 2. How many times has this person been bribed?
In Python3: