You are given a list of integers. The list contains copies of the same number and a single copy of another number. Your task is to find what number occurs only once.
For example, when the list is , the desired number is . Similarly, when the list is , the number to find is .
In a file onlyone.py
, implement the function find_number
that takes the list of numbers as a parameter and returns the number with one occurrence only. You may assume that the list contains at least three numbers so that the answer is always unique.
You must implement an efficient solution with a time complexity . For example, you cannot afford to go through all numbers on the list and count the occurrences of each number separately.
In the last test case of the following code template, the list contains copies of the number and one copy of the number . Your function should finish quickly in this test case too.
def find_number(numbers): # TODO if __name__ == "__main__": print(find_number([1, 1, 1, 2])) # 2 print(find_number([1, 1, 2, 1])) # 2 print(find_number([1, 2, 1, 1])) # 2 print(find_number([2, 1, 1, 1])) # 2 print(find_number([5, 5, 5, 3, 5])) # 3 print(find_number([1, 100, 1])) # 100 numbers = [1] * 10**5 + [2] print(find_number(numbers)) # 2