"Lonely Integer" Python implementation

Question 1

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 ≤ Aᵢ ≤ 100, ∀ i ∈ [1,N]

Output Format

Output S, the number that occurs only once.

Solution

#!/usr/bin/pyfrom collections import Counterdef 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 Noneif __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/pydef 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)

Question 2

You are right on all 3 counts. However, the problem has an \$O(1)\$ space-wise solution. Hint: think ofxor.

Question 3

@vnp, forsolution 2 yes.

Question 4

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 ahistogram() function, when you could swap it out forCounter(). That will make your code a little easier to read, because when I readCounter(), I immediately know what it does; if I seehistogram() 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 explicitreturn None; Python will automatically returnNone if it drops out the end of a function.
Rather than iterating over the tuples inCounter(array).items() and picking out the element/frequency by numeric index, it would be better to use tuple unpacking in thefor loop:
```
  for elem, frequency in histogram(ary).items():      if frequency == 1:          return elem
```

You could also just use themost_common() method ofCounter, 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.

alexwlchan 8,6751 gold badge23 silver badges55 bronze badges · Accepted Answer · 2024-11-30 08:08:48Z

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 ahistogram() function, when you could swap it out forCounter(). That will make your code a little easier to read, because when I readCounter(), I immediately know what it does; if I seehistogram() 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 explicitreturn None; Python will automatically returnNone if it drops out the end of a function.
Rather than iterating over the tuples inCounter(array).items() and picking out the element/frequency by numeric index, it would be better to use tuple unpacking in thefor loop:
```
  for elem, frequency in histogram(ary).items():      if frequency == 1:          return elem
```

You could also just use themost_common() method ofCounter, 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.

Movatterモバイル変換

Stack Exchange Network

"Lonely Integer" Python implementation

Problem Statement

Input Format

Constraints

Output Format

Solution

Solution 2

1 Answer1

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS