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?
# initialize the number of moves
moves = 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
Q = [P-1 for P in Q]
# Loop through each person (P) in the queue (Q)
for i,P in enumerate(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 position
if P - i > 2:
# 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
for j in range(max(P-1,0),i):
if Q[j] > P:
moves += 1