15
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Can you give numpy a try ? stackoverflow.com/a/35549699 \$\endgroup\$
    – aki
    Aug 10 '20 at 17:26
  • 1
    \$\begingroup\$ The only way to find out about better algorithms (not brute force) is to either see them used or be a mathematician (or be good at google for clever algorithms). \$\endgroup\$ Aug 10 '20 at 21:12
  • \$\begingroup\$ @anki I can not, this is a test, where you can not use the scientific python libraries, like pandas, numpy, scipy. \$\endgroup\$ Aug 11 '20 at 12:47
  • 3
    \$\begingroup\$ If you don't sort, you can just linearly go through the list and keep a map on the side with the count. If we say that the list is n elements of k different numbers, this solution would be O(n) in time and O(k) in space. \$\endgroup\$
    – bracco23
    Aug 13 '20 at 7:51
42
\$\begingroup\$

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.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ That's clever. I learn something new every day. \$\endgroup\$ Aug 10 '20 at 21:10
  • 14
    \$\begingroup\$ Obligatory 1-line implementation of the above: return functools.reduce(operator.xor, A) \$\endgroup\$
    – AJNeufeld
    Aug 11 '20 at 6:15
  • 12
    \$\begingroup\$ Not only would I argue that this is not widely known, it also only works if there is a single number that is repeated an odd amount of times. If there are multiple odd repeats, you won't magically get a list of all offending numbers, you'll just get a (for all intents and purposes) random number. \$\endgroup\$
    – AnnoyinC
    Aug 11 '20 at 18:18
  • 6
    \$\begingroup\$ @vnp I've never seen this before and think it's great. However, while I think this answer would be really cool for Stack Overflow it misses the mark for Code Review. I know you're posting it as an "extended comment" but that's not really a thing, since now it's on top by a wide margin and doesn't review OP's code. Maybe in the future you could post it as an actual comment, either broken up as two comments or a link to another place explaining it? \$\endgroup\$ Aug 11 '20 at 18:45
  • 6
    \$\begingroup\$ Note that this algorithm will return 0 if 0 is unpaired and if there are no unpaired numbers. Unless it is guaranteed that there is exactly one unpaired number, a separate check is needed to see how many zero elements there are when the XOR procedure returns 0. \$\endgroup\$
    – Mark H
    Aug 11 '20 at 19:05
16
\$\begingroup\$

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.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ I would use [k for k,v in my_counter.items() if v % 2] instead \$\endgroup\$ Aug 11 '20 at 7:11
  • 4
    \$\begingroup\$ Even better: next(k for k, v in counter.items() if v % 2), since you know there is only one. \$\endgroup\$
    – Graipher
    Aug 11 '20 at 9:05
  • 2
    \$\begingroup\$ That would be O(N) average case or does Counter always gets a perfect hash? otherwise it would be worst case O(N**2) using hash or O(n lg N) using red-black tree. \$\endgroup\$
    – Surt
    Aug 12 '20 at 20:10
  • \$\begingroup\$ @Surt IIRC the hash used is just the integer itself, and the hashtable implementation makes some efforts to keep that from being a problem for well-crafted inputs targeting a particular table size like [1, 65, 129, ...], but it's a best-effort to satisfy common cases, and malicious inputs are easy to construct. \$\endgroup\$ Aug 12 '20 at 23:54
14
\$\begingroup\$

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()
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Until I read vnp's answer this is how I would have done it. \$\endgroup\$ Aug 10 '20 at 21:13
  • 3
    \$\begingroup\$ @MartinYork this would be the best solution for non integers or if we cannot grant exactly one number to be present odd number of times in which case it can reveal all such numbers or tell that there is no such number. \$\endgroup\$
    – slepic
    Aug 11 '20 at 4:35
  • 4
    \$\begingroup\$ @MartinYork, this is still how I'd do it in any situation except a "clever coding" competition. It's more robust against unexpected situations, such as two unpaired elements. \$\endgroup\$
    – Mark
    Aug 12 '20 at 0:01
  • 2
    \$\begingroup\$ @Mark: I would have histogrammed into an array of counters (or hash table is the keys can be scattered), then looked for odd counts. Although using 1-bit counters (and thus toggling) will basically reduce to set add / remove. I'd probably avoid actually removing elements from a dictionary after seeing a pair if I was using a hash table, since that costs more work and might slow down seeing a 3rd one. (Unless there are a lot of unique pairs, so freeing up space to keep the hash table small is good.) \$\endgroup\$ Aug 12 '20 at 0:08
  • 2
    \$\begingroup\$ In this case, probably for a large input array, you'd use a space-efficient hash set and actually take the time to decide between adding or removing an element, instead of just finding and flipping a boolean counter. Worst case still O(N) space if you see all the unique elements first, before finding any pairs. But hopefully in most cases, you can get away with much less than O(N) space by recycling entries. But for medium to small input arrays, where the typical space for an add-only hash table still fits in L2 or even L1 cache, you might just index and flip a counter. \$\endgroup\$ Aug 13 '20 at 8:03
2
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ If your values aren't small to medium integers, use a hash table (dictionary) to map num -> count, but yes, histogram and then look for odd count buckets is the obvious way here. The pythonic version of this is apparently collections.Counter, as suggested by a different answer. \$\endgroup\$ Aug 12 '20 at 0:18
  • \$\begingroup\$ If you have an upper bound on max, you can avoid the first pass through the list, especially useful if that max is much less than N (i.e. there are a lot of repeats.) Or use a data structure that can realloc and grow on the fly for amortized O(1) if you pick too low. To minimize cache footprint (and the amount of memory you have to zero to start with), the count array can be bytes instead of int, or even single-bit counters because you only care about the low bit of the count, and wrapping the high part doesn't affect that. \$\endgroup\$ Aug 12 '20 at 0:18
  • 1
    \$\begingroup\$ (If the array values are scattered, a hash table could perform better than a very sparse array where each element you access is in a different page of virtual memory.) \$\endgroup\$ Aug 12 '20 at 0:22
  • \$\begingroup\$ Yea I would use HashMaps in reality (I love them), but those have O(log n) accessing time in worst case so the O(n) wouldn't be guaranteed or harder to argue. And your optimizations are totally true, this is a very basic way and only targets speed not memory. \$\endgroup\$ Aug 12 '20 at 10:02
  • \$\begingroup\$ Java 8 HashMap was my first google hit. It provides O(1) amortized average time. I'd be surprised if the worst case is as good as log(n), probably n when it has to reallocate to grow. But it'll grow exponentially (e.g. by a factor of 2) to make growth as infrequent as O(N / N) = O(1) on average. Perhaps with O(log(N)) you're thinking of an ordered map based on a tree? HashMap is unordered, like C++ std::unordered_map or unordered_set. \$\endgroup\$ Aug 12 '20 at 17:28
0
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ Fails solution([0]). \$\endgroup\$ Aug 13 '20 at 14:26
  • \$\begingroup\$ @superbrain yes, thanks. \$\endgroup\$
    – tevemadar
    Aug 13 '20 at 15:02

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.