Consider the same process as in the previous task, but now the goal is to count the number of rounds efficiently.
For example, when the list is , the rounds are , , and . Thus the number of rounds is four.
In a file fastrounds.py
, 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 in descending order and the number of rounds is . Your function should be fast in this test case too.
def count_rounds(numbers): # TODO if __name__ == "__main__": print(count_rounds([1, 2, 3, 4])) # 1 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