There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.
The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.
\$N % 2 = 1\$ (N is an odd number)
Output S, the number that occurs only once.
#!/usr/bin/py from collections import Counter def histogram(ary): """ Creates a histogram of the given array. Args: ary: The array. Returns: The dictionary with key as number and value as count. """ return Counter(ary) def lonelyinteger(ary): """ Finds the unique element in the array. Args: ary: The input array. Returns: Number or None """ for frequency in histogram(ary).items(): if frequency == 1: return frequency return None if __name__ == '__main__': a = int(raw_input()) b = map(int, raw_input().strip().split(" ")) print lonelyinteger(b)
The solution works perfectly fine. But in the process of learning problem-solving, I am interested in a few things:
- I don't think that the information like N is odd or maximum limit of 100 is related to my solution. Is there some optimizations I am missing?
- What about the space complexity? I think it's \$O(N)\$ + size of the histogram.
- Runtime seems linear i.e \$O(N)\$.
It includes the factors like why N should be odd.
1 ^ 1 ^ 2 ^ 2 ^ 3
#!/usr/bin/py def lonelyinteger(a): res = 0 for each in a: res ^= each return res if __name__ == '__main__': a = input() b = map(int, raw_input().strip().split(" ")) print lonelyinteger(b)