5
\$\begingroup\$

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\$ (N is an odd number)

\$0≤A_{i}≤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 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)\$.

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)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You are right on all 3 counts. However, the problem has an \$O(1)\$ space-wise solution. Hint: think of xor. \$\endgroup\$ – vnp Sep 24 '15 at 6:53
  • \$\begingroup\$ @vnp, for solution 2 yes. \$\endgroup\$ – CodeYogi Sep 24 '15 at 7:24
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.