Find Elements occurring odd number of times in a list

Question

Let's say we need to find all the elements occurring an odd number of times in a sorted list in O(N) time and O(1) space complexity.

ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]        
output = [1,3,4,6]

We are not going to return a new list, perhaps will be overwrite the existing one

I have an approach which uses a hashing technique, but it results in O(N) space complexity.

I have tried bitwise manipulation using XOR, but I am not able to solve the question.

When you say O(1) space complexity perhaps the intention is to overwrite the existing list rather than allocating a new one? — Stuart, Jan 12 '22 at 16:54
Sorry for bit confusion, but lets say we want to return the same list. We are not going to use any extra space — Rohit Saini, Jan 12 '22 at 16:54

Stuart · Accepted Answer · 2022-01-13T11:50:41.600

Iterate through the list, counting cases where the present item is the same as the previous one, and overwriting towards the start of the list when it is different and the count is an odd number.

This solution overwrites the existing list rather than allocating a new one, and has O(N) time complexity. Because the new list will be shorter, we have to pop the remaining items from the end of it. (We would normally splice using ls = ls[position:] but that would assign a new list, which isn't allowed.)

def keep_odd_elements(ls):
    count = 0
    write_position = 0
    previous = object()
    for item in ls:
        if item == previous:
            count += 1
        else:
            # Write the odd-counted numbers towards the start of the list
            if count % 2:
                ls[write_position] = previous
                write_position += 1
            count = 1
        previous = item
    if count % 2:
        ls[write_position] = previous
        write_position += 1
    # Remove the leftover items at the end of the list
    for _ in range(write_position, len(ls)):
        ls.pop()
    
ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]
keep_odd_elements(ls)
print(ls)   # [1, 3, 4, 6]

If we remove the requirement not to allocate a new list, then we can write this much more elegantly:

def get_odd_elements(ls):
    count = 0
    for a, b in zip([object()] + ls, ls + [object()]):
        if a == b:
            count += 1
        else:
            if count % 2:
                yield a
            count = 1

print(list(get_odd_elements([1,2,2,3,3,3,4,5,5,6,6,6,6,6])))

Great Man! Thats gonna work. But lets say my data is not sorted. Can i still achieve my solution in constant space — Rohit Saini, Jan 12 '22 at 17:24
It doesn't rely on the list being sorted as such but on equal elements being grouped. e.g. `[2,2,2,1,1,3,3,3,3]` would also work. I don't know how to do it if that isn't the case. Note that the [space complexity of `sort` is O(1) best case, O(N) worst case](https://stackoverflow.com/questions/48759175/what-is-the-space-complexity-of-the-python-sort) — Stuart, Jan 12 '22 at 17:29
Yes i meant the clubbing only. Looks like if data is scattered and not grouped its very hard to achieve it in constant space. — Rohit Saini, Jan 12 '22 at 17:50

Jut · Answer 2 · 2022-01-13T16:36:27.547

This is C++ code that runs in O(n) and use O(1) auxiliary memory.

The idea behind this code is very simple, we start from left and counting number of occurrence of a number x until we arrive to a number y that not equal x, because of our input is sorted it guarantee that x never appear after y. So it's sufficient to check if number of occurrence of x be odd.

Note that, if the array is not sorted it's provable that, you can't do better than O(nlogn)

 //Find odd numbers in given sorted list

#include <stdio.h>

int main(){
    
  int ArrayLength;
  scanf("%d",&ArrayLength);
  int array[ArrayLength];
  

  //Read input sorted array
  for ( int i = 0; i < ArrayLength; i++)
       scanf("%d",&array[i]);
       

  // Find numbers with odd occurrence 
  int PreviousLocalOdd=array[0];
  int LocalOdd=1;
  for ( int i = 1; i < ArrayLength; i++)
    {

        if (array[i]==PreviousLocalOdd)
            LocalOdd++;
        
        if(array[i]!= PreviousLocalOdd)    
          {  
                if(LocalOdd % 2==1)
                    printf("%d",array[i-1]);
            LocalOdd=1;
            PreviousLocalOdd=array[i];
          }
     
    }
       if(LocalOdd % 2==1)
        printf("%d ",array[ArrayLength-1]);


return 0;
}

Find Elements occurring odd number of times in a list

2 Answers2