"Lonely Integer" Python implementation

Question

Problem Statement

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.

Input Format

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.

Constraints

1 ≤ N < 100

N % 2 = 1 (i.e. N is an odd number)

0 ≤ Ai ≤ 100, ∀ i ∈ [1,N]

Output Format

Output S, the number that occurs only once.

Solution

#!/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] == 1:
 return frequency[0]
 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 optimization 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).

Solution 2

It includes the factors like why N should be odd.

Example: 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)

• vnp: You are right on all 3 counts. However, the problem has an \$O(1)\$ space-wise solution. Hint: think of xor.
• CodeYogi: @vnp, for solution 2 yes.

Answer 1

A few quick comments:

• Indeed, your solution doesn’t require N to be odd. You’ve solved the slightly more general problem of finding a lonely integer in an array where every other element occurs at least twice, but could occur more often than that.

  Likewise, the restriction that N ≤ 100 isn’t used, but I can’t think of how that could be used in a solution.

• I don’t know why you’ve defined a histogram() function, when you could swap it out for Counter(). That will make your code a little easier to read, because when I read Counter(), I immediately know what it does; if I see histogram() then I have to check I’ve understood the definition.

• When you iterate over the histogram, you should use .iteritems() instead of .items(); in Python 2.7 the latter is slower and more memory-expensive.

• You don’t need an explicit return None; Python will automatically return None if it drops out the end of a function.

• Rather than iterating over the tuples in Counter(array).items() and picking out the element/frequency by numeric index, it would be better to use tuple unpacking in the for loop:

   for elem, frequency in histogram(ary).items():
   if frequency == 1:
   return elem
  

You could also just use the most_common() method of Counter, and take the last element of that – but at that point you’re barely doing any work, so that might not be in the spirit of the problem.