"Lonely Integer" Python implementation

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

• 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)

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 \leq 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 on 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.

StackExchange Code Review Q#105577, answer score: 2