[Python] Optimizing going through a long list?

Task is to make a code that goes through a list from 1,2...n where numbers are randomly placed and count the amount of iterations it takes to get all the numbers starting from 1.

For example [1,2,3,4] would take one iteration, while [1,3,2,4] would take two, one where 1,2 is taken and one where 3,4 is taken. But this exercise asks you to

implement the function count_rounds that takes the list as a parameter and returns the number of rounds. In this task, the list may be so long that it would be too slow to go through the whole list in each round. Your task is to find a more efficient way of computing the number of rounds.

In the last test case of the code template, the list contains the numbers 1,2,...,10^5 in descending order and the number of rounds is 10^5. Your function should be fast in this test case too.
​

I tried removing items from the list but I genuinely can't figure out how to make it fast enough to pass the test (around 10s).

My current attempt:

def count_rounds(numbers):
n = len(numbers)

result = 0
x=1
while x<n:
for number in numbers:
try:
if number>numbers[x]:
result+=1
except:
break
x+=1
return result+1

if __name__ == "__main__":
print(count_rounds([2, 5, 4, 1, 3])) # 4
print(count_rounds([1, 3, 2, 4])) # 2
print(count_rounds([4, 3, 2, 1])) # 4
print(count_rounds([1])) # 1
print(count_rounds([2, 1, 4, 7, 5, 3, 6, 8])) # 4

n = 10**5
numbers = list(reversed(range(1, n+1)))
print(count_rounds(numbers)) # 100000


the hashtag corresponds to the expected output, which is:

3
2
4
1
4
100000


instead.

Continue reading...