Finding the odd number out in an array

Question

I am trying to solve a problem where I'm given an array, such as [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] where all numbers are duplicated twice, excluding one number, and I need to return the number that is not duplicated.

I am trying to do it like this:

def findNumber(self, nums):

    if (len(nums) == 1):
        return nums[0]

    nums_copy = nums[:]

    for i in nums:
        nums_copy.remove(i)

        if i not in nums:
            return i
        else:
            nums_copy.remove(i)

However when it reaches the else statement, there is the following error:

ValueError: list.remove(x): x not in list

This is occurring when i is in nums_copy, so I do not understand why this error occurs in this situation?

Answer 1

An easier (and more efficient) way of doing this than your initial approach is with a Counter object:

 from collections import Counter

 singlet = Counter(nums).most_common()[-1][0]

The Counter object will create a dictionary-like object with the keys being the values in your list and the values being the number of times they appear. The most_common method will return a list of tuples of (value, count) sorted by count in decreasing order.

If you don't know how many singlets there will be, you can get a list of them with:

[k for k, v in Counter(nums).items() if v == 1]

---

Complexity:

I said my top solution was more efficient because your original implementation iterates through your list and for each item calls both remove and in which is going to get you to something like O(n²) complexity. In the Counter implementation the construction of the Counter object only does a single pass through the entire list. There is probably a sort going on when most_common is called so I'm guessing the complexity is about O(n log n). @Stefan Pochman has corrected me on this: Python uses the Timsort algorithm which will be very efficient in a case like this (if all but one of the numbers appear twice, the list is effectively almost completely sorted already) so its complexity will about about O(n).

Answer 2

You already nums_copy.remove(i) so you can't nums_copy.remove(i) again

You could do:

a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]

def get_single_instance(array):
  d = {}

  for item in a:
    if item not in d:
      d[item] = 1
    else:
      d[item] += 1

  print d

  for k, v in d.iteritems():
    if v == 1:
      return k

print get_single_instance(a)

Result: 9

Answer 3

The best algorithm is to use XOR to find the odd number.

def find_number(nums):
    s = 0 
    for n in nums:
        s ^= n 
    return s 


a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] 
print(find_number(a))

Answer 4

If the array is sorted, we can find the answer in O(log n) time and O(1) extra space. Consider that repeated number pairs start on odd or even indexes depending on where the single element is:

              0  1  2  3  4  5  6  7  8  9   10
             [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]
even indexes: x     x     x     x
odd indexes:                             x

search:                      ^  (0 + 11) / 2 = 5
                         [2, 2] pair starting on even index
                                so the singleton must be ahead

                                      ^  (6 + 11) / 2 = 8
                                     [9] singleton found in two steps!

Answer 5

Try this list comprehension. It goes through each element and checks if it is duplicated, and if it isn't, it lets it stay in the new list. It then gets the zeroth element of the new list:

a=[0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]
[e for e in a if a.count(e)==1][0]

Answer 6

For the list A we can first sort it so it takes the form similar to: [1,1,4,4,5,7,7]. We check if every second number is the same with the one coming after it. If not it means that the number is the odd one.

def findNumber(A):
        A=sorted(A)
        l=len(A)
        for i in range(0,l,2):
            if i<l-1:
                if A[i]!=A[i+1]:
                    break
            else:
                break
        return A[i]

Answer 7

This is a very long method of doing things. As suggested you could use nums_copy.remove(i) or you could implement this is a much simpler manner using count():

def findNumber(self, nums):

    for i in nums:

        val = nums.count(i)

        if val == 1:
            return i

This will return the single number. This method is fine as long as you do not have multiple values, if so it will return only the last one. You could otherwise return a list which would store multiple values like so:

def findNumber(self, nums):
    values = []
    for i in nums:

        val = nums.count(i)

        if val == 1:
            values.append(i)

    return values

Answer 8

Assuming a sorted iterable (otherwise sort it), here is the first occurrence of a non-duplicate pair:

import more_itertools as mit


iterable = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] 
next(x for x, y in mit.windowed(iterable, n=2, step=2) if x != y)
# 9

An alternative way to create non-overlapping pairs:

next(x for x, y in mit.sliced(iterable, 2) if x != y)
# 9

more_itertools is a third-party library, > pip install more_itertools.

Answer 9

A good way to do this in Python is with collections.Counter for O(n) complexity:

from collections import Counter

def solution(A):
    for x, occ in Counter(A).items():
        if occ % 2:
            return x

This will also generalize to return any number that occurs an odd number of times in the array.

Answer 10

Python 3.6 above

---

Solution 1

def solution(A):
    # write your code in Python 3.6
    result =0
    for i in A:
        result ^= i
    return result

---

Solution 2:

from itertools import groupby


def solution(A):
    # write your code in Python 3.6
    for key, group_list in groupby(sorted(A)):
        if len(list(group_list)) % 2 == 1:
            return key

Time complexity: O(N)

Answer 11

For anyone working with NumPy, this should be competitive in speed with other answers here:

>>> def get_single_instance_np(arr: np.ndarray):
...     return np.asscalar(arr[np.bincount(arr) == 1])

>>> print(get_single_instance(a))
9

This just returns elements for which their count equals 1.