How to make space complexity as O(1)

Question

I am trying to answer for the below question : You have an array of integers, such that each integer is present an odd number of time, except 3 of them. Find the three numbers.

so far I came with the brute force method :

 public static void main(String[] args) {
    // TODO Auto-generated method stub

    int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
    FindEvenOccurance findEven = new FindEvenOccurance();
    findEven.getEvenDuplicates(number);

  }

  // Brute force
  private void getEvenDuplicates(int[] number) {

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i : number) {

      if (map.containsKey(i)) {
        // a XOR a XOR a ---- - -- - - odd times = a
        // a XOR a ---- -- -- --- - even times = 0
        int value = map.get(i) ^ i;
        map.put(i,value);
      } else {
        map.put(i, i);
      }
    }

    for (Entry<Integer, Integer> entry : map.entrySet()) {

      if (entry.getValue() == 0) {
        System.out.println(entry.getKey());
      }

    }
  }

It works fine but not efficient.

The o/p :

1
5
6
8

But the questions specifies we need to do this in O(1) space and O(N) time complexity. For my solution, the time complexity is O(N) but space also O(N). Can some one suggest me a better way of doing this with O(1) space ?

Thanks.

Answer 1

I spent some time solving this problem. Seems that I found solution. In any case I believe, that community will help me to check ideas listed below.

First of all, I claim that we can solve this problem when the number of non-paired integers is equal to 1 or 2. In case of 1 non-paired integer we just need to find XOR of all array elements and it'll be the answer. In case of 2 non-paired integers solution becomes more complicated. But it was already discussed earlier. For example you can find it here.

Now let's try to solve problem when the number of non-paired integers is equal to 3.

At the beginning we also calculate XOR of all elements. Let's denote it as X.

Consider the i-th bit in X. I assume that it's equal to 0. If it's equal to 1 the next procedure is practically the same, we just change 0 to 1 and vice versa.

So, if the i-th in X bit is equal to 0 we have two possible situations. One situation is when all non-paired integers have 0 in the i-th bit. Another situation is when one non-paired integer has 0 in the i-th bit, and two non-paired integers have 1 in i-th bit. This statement is based on simple XOR operation properties. So we have one or three non-paired integers with 0 in the i-th bit.

Now let's divide all elements into the two groups. The first group is for integers with 0 in the i-th bit position, the second is for integers with 1 in the i-th bit position. Also our first group contains one or three non-paired integers with '0' in the i-th bit.

How we can obtain the certain number of non-paired integers in the first group? We just need to calculate XOR of all elements in the second group. If it's equal to zero, than all non-paired integers are in the first group and we need to check another i. In other case only one non-paired integer is in the first group and two others are in the second and we can solve problem separately for this two groups using methods from the beginning of this answer.

The key observation is that there's i such that one non-paired integer has i-th bit that differs from the i-th bits of the two other non-paired integers. In this case non-paired integers are in both groups. It's based on the fact that if there's no such i then bits in all positions in non-paired integers are similar and they are equal to each other. But it's impossible according to the problem statement.

This solution can be implemented without any additional memory. Total complexity is linear with some constant depending on the number of bits in array elements.

Answer 2

Unfortunately it is not possible to achieve such a solution with O(1) space and O(n) complexity if we use a strict sense of space, i.e. O(1) space is bound by the max space used in the input array.

In a weak sense of space, where one arbitrary large Integer number does still fit into O(1), you can just encode your counter into the bits of this one integer. Start with all bits set to 1. Toggle the n-th bit, when you encounter number n in the input array. All bits remaining 1 at the end represent the 3 numbers which were encountered an even number of times.