Finding an element in an array that isn't repe

Question

After reading this interesting question I was reminded of a tricky interview question I had once that I never satisfactorily answered:

You are given an array of n 32-bit unsigned integers where each element (except one) is repeated a multiple of three times. In O(n) time and using as little auxiliary space as possible, find the element of the array that does not appear a multiple of three times.

As an example, given this array:

1 1 2 2 2 3 3 3 3 3 3

We would output 1, while given the array

3 2 1 3 2 1 2 3 1 4 4 4 4

We would output 4.

This can easily be solved in O(n) time and O(n) space by using a hash table to count the frequencies of each element, though I strongly suspect that because the problem statement specifically mentioned that the array contains 32-bit unsigned integers that there is a much better solution (I'm guessing O(1) space).

Does anyone have any ideas on how to solve this?

Answer 1

It can be done in O(n) time and O(1) space.

Here is how you can do it with constant space in C#. I'm using the idea of "xor except with 3-state bits". For every set bit, the "xor" operation increments the corresponding 3-state value.

The final output will be the number whose binary representation has 1s in places that are either 1 or 2 in the final value.

void Main() {
    Console.WriteLine (FindNonTriple(new uint[] 
                        {1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3} ));
    // 1

    Console.WriteLine (FindNonTriple(new uint[] 
                        {3, 2, 1, 3, 2, 1, 3, 2, 1, 4, 4, 4, 4} ));
    // 4
}

uint FindNonTriple(uint[] args) {
    byte[] occurred = new byte[32];

    foreach (uint val in args) {
        for (int i = 0; i < 32; i++) {
            occurred[i] = (byte)((occurred[i] + (val >> i & 1)) % 3);
        }
    }

    uint result = 0;
    for (int i = 0; i < 32; i++) {
        if (occurred[i] != 0) result |= 1u << i;
    }
    return result;
}

Answer 2

The obvious solution to do it in constant space is to sort it using an in place algorithm, and then scan once over the array.

Sadly this requires usually O(n log n) time and O(1) space.

But as the entries have a limited key length (32 bit) you can use as sort algorithm radix sort (there exist in place radix sort, they are not stable, but that doesnt matter here). There you have O(n) time and O(1) space.

EDIT: Btw you could use this approach to find also ALL numbers that appear not a multiple of 3 times, in case you would allow that more than one number could have this property.

Answer 3

You're looking for an item with a rep-count that's non-zero (mod 3). I think I'd do it recursively:

1. split the array in half
2. find items with rep count that's non-zero (mod 3) in each half
3. merge the halves, keeping counts for unequal keys, and adding the counts for equal keys
4. strike out any with count = 0 (mod 3)
5. return that as the set of values for the current part of the input.

Without even trying to optimize things beyond the basic algorithm (e.g., not worrying about storing only two bits per count), this seems to do pretty well. I've included code to generate a reasonably large test case (e.g., 1500+ items) and print out the sizes of the maps it's creating. At any given time, it seems to have a maximum of around 50 items in the maps it creates (i.e., it only uses two maps at a time, and the largest I've seen is around 25 items). Technically, as it stands I believe this is currently something like O(N log N), but if you switched to a hash-based container, I believe you'd expect O(N).

#include <map>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <time.h>

class zero_mod { 
    unsigned base;
public:
    zero_mod(unsigned b) : base(b) {}

    bool operator()(std::pair<int, int> const &v) { 
        return v.second % base == 0; 
    }
};

// merge two maps together -- all keys from both maps, and the sums 
// of equal values.
// Then remove any items with a value congruent to 0 (mod 3)
//
std::map<int, int> 
merge(std::map<int, int> const &left, std::map<int, int> const &right) { 
    std::map<int, int>::const_iterator p, pos;
    std::map<int, int> temp, ret;

    std::copy(left.begin(), left.end(), std::inserter(temp, temp.end()));
    for (p=right.begin(); p!=right.end(); ++p) 
        temp[p->first] += p->second;
    std::remove_copy_if(temp.begin(), temp.end(), 
                        std::inserter(ret, ret.end()), 
                        zero_mod(3));
    return ret;
}   

// Recursively find items with counts != 0 (mod 3):    
std::map<int, int> 
do_count(std::vector<int> const &input, size_t left, size_t right) { 
    std::map<int, int> left_counts, right_counts, temp, ret;

    if (right - left <= 2) {
        for (size_t i=left; i!=right; ++i) 
            ++ret[input[i]];
        return ret;
    }
    size_t middle = left + (right-left)/2;
    left_counts = do_count(input, left, middle);
    right_counts = do_count(input, middle, right);
    ret = merge(left_counts, right_counts);

    // show the size of the map to get an idea of how much storage we're using.
    std::cerr << "Size: " << ret.size() << "\t";
    return ret;
}

std::map<int, int> count(std::vector<int> const &input) { 
    return do_count(input, 0, input.size());
}

namespace std { 
    ostream &operator<<(ostream &os, pair<int, int> const &p) { 
        return os << p.first;
    }
}

int main() {
    srand(time(NULL));
    std::vector<int> test;

    // generate a bunch of data by inserting packets of 3 items    
    for (int i=0; i<100; i++) {
        int packets = std::rand() % 10;
        int value = rand() % 50;
        for (int i=0; i<packets * 3; i++) 
            test.push_back(value);
    }

    // then remove one item, so that value will not occur a multiple of 3 times
    size_t pos = rand() % test.size();
    std::cerr << "Removing: " << test[pos] << " at position: " << pos << "\n";

    test.erase(test.begin()+pos);

    std::cerr << "Overall size: " << test.size() << "\n";

    std::random_shuffle(test.begin(), test.end());

    // Note that we use a map of results, so this will work if multiple values
    // occur the wrong number of times.    
    std::map<int, int> results = count(test);

    // show the results. Should match the value shown as removed above:
    std::copy(results.begin(), results.end(), 
        std::ostream_iterator<std::pair<int, int> >(std::cout, "\n"));
    return 0;
}