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.

Answer 3

There's two ways to look at your problem.

The first way, as a mathematical problem with an infinite set of integer, it seems unsolvable.

The second way, as a computing problem with a finite integers set, you've already solved it (congratulations !). Why ? Because storage space is bounded by MAX_INT, independently of N.

NB an obvious space optimization would be to store the values only once, erasing the previous value for even counts, you'll gain half the space.

About the other answers by @Lashane and @SGM1: they also solve the "computing" problem, but are arguably less efficient than yours in most real-world scenarios. Why ? Because they pre-allocate a 512MB array, instead of allocating proportionaly to the number of different values in the array. As the array is likely to use much less than MAX_INT different values, you're likely to use much less than 512MB, even if you store 32bits for each value instead of 1. And that's with 32 bits integers, with more bits the pre-allocated array would grow exponentially, OTOH your solution only depends on the actual values in the array, so is unaffected by the number of bits of the system (i.e. max int value).

See also this and this for better (less space) algorithms.

Answer 4

consider for example the numbers allowed are of size 4 bits, which means the range of numbers allowed from 0 to 2⁴-1 which is a constant number 16, for every possible input we run over all array and xor the occurrence of this number, if the result of xor is zero, we add current value to the overall result. this solution is O(16N) which is O(N) and use only one extra variable to evaluate the xor of current number which is O(1) in terms of space complexity.

we can extend this method to our original problem, but it will have a very big constant number in terms of run time complexity which will be proportional to the number of bits allowed in the original input.

we can enhance this approach by run over all elements and find the Most significant bit over all input data, suppose it is the 10^th bit, then our run time complexity will become O(2¹⁰N) which is also O(N).

another enhancement can be found in the below image, but still with the worst case complexity as discussed before.

finally I believe that, there exist another better solution for this problem but I decided to share my thought.

Edit:

the algorithm in the image may not be clear, here is some explanation to the algorithm.
it start with the idea of trying to divide the elements according to there bits, in other words make the bits as a filter, at each stage xor the divided elements, until the xor result is zero, then it is worth to check this group one by one as it will for sure contain at least one of the desired outputs. or if two consultative filters result in the same size we will stop this filter, it will be more clear with example below.
input: 1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9
we start by dividing the elements according to the Least significant bit.
1^st bit zero : 6,4,4,8,8,4,6,8,8
6 xor 4 xor 4 xor 8 xor 8 xor 4 xor 6 xor 8 xor 8 = 4
so we will continue dividing this group according to the 2^nd bit.
1^st bit zero and 2^nd bit zero : 4,4,4,8,8,8,8
4 xor 4 xor 4 xor 8 xor 8 xor 8 xor 8 xor 8 = 4.
so we will continue dividing this group according to the 3^rd bit.
1^st bit zero and 2^nd bit zero and 3^rd bit zero : 8,8,8,8
8 xor 8 xor 8 xor 8 = 0
so we will go through every element under this filter as the result of xor is zero and we will add 8 to our result so far.
1^st bit zero and 2^nd bit zero and 3^rd bit one : 4,4,4
4 xor 4 xor 4 = 4
1^st bit zero and 2^nd bit zero and 3^rd bit one and 4^th bit zero : 4,4,4
4 xor 4 xor 4 = 4.
so we will stop here as this filter contain the same size as previous filter
now we will go back to the filter of 1^st and 2^nd bit
1^st bit zero and 2^nd bit one : 6,6
6 xor 6 = 0.
so we will go through every element under this filter as the result of xor is zero and we will add 6 to our result so far.
now we will go back to the filter of 1^st bit
1^st bit one : 9,5,9,7,9,1,1
now we will continue under this filter as the same procedure before.
for complete example see the above image.

Answer 5

Your outline of the problem and the example do not match. You say you're looking for 3 integers in your question, but the example shows 4.

I'm not sure this is possible without additional constraints. It seems to me that worst case size complexity will always be at least O(N-6) => O(N) without a sorted list and with the full set of integers.

If we started with sorted array, then yes, easy, but this constraint is not specified. Sorting the array ourselves will be too time or space complex.

Answer 6

My stab at the an answer, using Lashane's proposal in slightly different way:

char negBits[268435456]; // 2 ^ 28 = 2 ^ 30 (number of negative integer numbers) / 8 (size of char)
char posBits[268435456]; // ditto except positive

int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

for (int num : number){
   if (num &lt 0){
       num = -(num + 1);// Integer.MIN_VALUE would be excluded without this + 1
       negBits[ &lt&lt 4] ^= ((num & 0xf) >> 1);
   }
   else {
       posBits[num &lt&lt 4] ^= ((num & 0xf) >> 1);
       // grab the rite char to mess with
       // toggle the bit to represent the integer value.
   }
}

// Now the hard part, find what values after all the toggling:

for (int i = 0; i &lt Integer.MAX_VALUE; i++){
    if (negBits[i &lt&lt 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + (-i - 1));
    }
    if (posBits[i &lt&lt 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + i);
    }
}

As per discussion in comments, below points are worth noting to this answer:

• Assumes Java in 32 bit.
• Java array have an inherent limit of Integer.MAX_INT