Finding an element without pair in a list O(n**2)

Question

I'm practicing algorithms, and I just can not come up with a faster solution to this problem, but I'm not hitting the benchmark.

Problem: In a large list of large integers, I must find the one element, that is present in odd numbers. E.g. [1,1,1,1, 2,2, 3,3,3, 4,4,4,4].

I wrote several solutions, but I can not increase the speed of the execution.

import random

def testdata():
  space = []
  for i in range(10000):
    space = (
        space
        + [random.randint(0,1000000000)]
        * (random.randint(1,10) * 2)
    )
  odd = random.randint(0,1000000000)
  print(odd)
  space = space + [odd]
  random.shuffle(space)
  return space


def solution(A):
  A.sort()
  index = 0
  while True:
    count = A.count(A[index])
    if count%2:
      return(A[index])
    else:
      index = index + count


def solution_b(A):
  for elem in set(A):
    if A.count(A)%2:
      return(elem)

I'm not only looking for a better solution, but I'd appreciate it if someone explained, how to approach this kind of Big O notation problems. Without using pandas or numpy, etc.

Answer 1

This is not a review, but an extended comment.

The linear time/constant space solution is too well known to be spelled out again. However, here it goes.

XOR of two equal numbers is 0, and XOR of a number and 0 leaves the number unchanged. XOR is commutative and associative operation; we may perform it in any order we wish, and arrive to the same result. In other words, if we XOR all of them, each pair of numbers would cancel to 0, and the final result would be the number without a pair, the one we are looking for.

Answer 2

You can use collections.Counter to solve this problem with a time complexity of O(N) and a space complexity of also O(N).

from collections import Counter

my_array = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
my_counter = Counter(my_array)

# Thanks to @AlexeyBurdin and @Graipher for improving this part.
print(next(k for k, v in my_counter.items() if v % 2))

This will print out the first element which occurs an odd number of times.

You can read more about collections.Counter here.

This is the simplest and fastest solution I can think of.

Answer 3

In both solutions, A.count() searches the entire list.

Try using a set. For each element in the list, check if the element is in the set. If it isn't in the set, add it; if it is in the set then remove it. When you reach the end of the list, the set will contain only items that had an odd number of them in the list.

def solution(A):
    odd = set()

    for item in A:
        if item in odd:
            odd.remove(item)
        else:
            odd.add(item)

    return odd.pop()

Answer 4

Okay so I do not really understand the issue or why this should not be trivially linear. Note: I dont know python or those fancy shortcuts used in previous answers. Just using simple basic functions (Java style, translate to whatever floats your boat):

1. Iteration through an array: O(n)
2. Array element access: O(1) it seems.. (https://stackoverflow.com/questions/37120776/accessing-elements-really-o1)

So..

int[] numbers = [1,1,2,2,3,3,3];
int maxNumber = 0; //or maxNegative if you include negative

//find maxNumber by iterating once in O(n)
for(int i = 0; i < numbers.length; i++){
     if(numbers[i]>maxumber)
          maxNumber = numbers[i];
     }
}
 
//new array of length maxNumber
int[] numberOccurences = new int[maxNumber];

//initialize array in O(n)
for(int i = 0; i < numberOccurences.length; i++){
    numberOccurences[i] = 0;
}
   
//count all number occurences in O(n)
for(int num : numbers){
    numberOccurences[num]++;
}

//get all numbers with odd occurences in O(n)
for(int i = 0; i < numberOccurences.length; i++){
     if(numberOccurences[i]%2!=0){
           print(i)
     }
 }

So as far as I can see that solves it in 4x O(n) = O(n) with just simple loops. If you need negative numbers, just use 2 arrays, that wont change anything. If you have double values, multiply them by 10 to the power of maximum number of decimal places. Please correct me if I am wrong.

Answer 5

A refinement for your first solution(): after you sort the list, you can just go through it in double-steps, comparing the neighboring elements. When they differ, the first one is what you are looking for:

def solution(A):
  A.sort()
  index = 0
  while True:
    if A[index] != A[index+1]:
      return A[index]
    index += 2

Like with the example sorted list from the question:

[1,1,1,1,2,2,3,3,3,4,4,4,4]
 1=1 1=1 2=2 3=3 3!4
                 ^ this is the one missing a pair

This approach has the complexity of the sorting algorithm, O(n log n) I would assume.

---

Then comes the comment below and handling the unlucky event of having the pair-less element at the very end.

Sticking to minimal modifications:

def solution(A):
  A.sort()
  index = 0
  while True:
    if index+1 >= len(A):
      return A[-1]
    if A[index] != A[index+1]:
      return A[index]
    index += 2

However if I wrote it from scratch, I would probably use a loop which simply exits and I would also cache len(A):

def solution(A):
  A.sort()
  limit = len(A) - 2
  index = 0
  while index<limit:
    if A[index] != A[index+1]:
      return A[index]
    index += 2
  return A[-1]