Suggest an Efficient Algorithm

Question

Given an Array arr of size 100000, each element 0 <= arr[i] < 100. (not sorted, contains duplicates)

Find out how many triplets (i,j,k) are present such that arr[i] ^ arr[j] ^ arr[k] == 0 Note : ^ is the Xor operator. also 0 <= i <= j <= k <= 100000

I have a feeling i have to calculate the frequencies and do some calculation using the frequency, but i just can't seem to get started.

Any algorithm better than the obvious O(n^3) is welcome. :)

It's not homework. :)

Answer 1

I think the key is you don't need to identify the i,j,k, just count how many.

Initialise an array size 100

Loop though arr, counting how many of each value there are - O(n)

Loop through non-zero elements of the the small array, working out what triples meet the condition - assume the counts of the three numbers involved are A, B, C - the number of combinations in the original arr is (A+B+C)/!A!B!C! - 100**3 operations, but that's still O(1) assuming the 100 is a fixed value.

So, O(n).

Answer 2

Possible O(n^2) solution, if it works: Maintain variable count and two arrays, single[100] and pair[100]. Iterate the arr, and for each element of value n:

• update count: count += pair[n]
• update pair: iterate array single and for each element of index x and value s != 0 do pair[s^n] += single[x]
• update single: single[n]++

In the end count holds the result.

Answer 3

Possible O(100 * n) = O(n) solution. it solve problem i <= j <= k. As you know A ^ B = 0 <=> A = B, so

long long calcTripletsCount( const vector<int>& sourceArray )
{
  long long res = 0;
  vector<int> count(128);
  vector<int> countPairs(128);
  for(int i = 0; i < sourceArray.size(); i++)
  {
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++)
      countPairs[j ^ sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i] ^ sourceArray[j]
    res += countPairs[sourceArray[i]]; // a ^ b ^ c = 0 if a ^ b = c, we add count of pairs (p1, p2) where sourceArray[p1] ^ sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i)
  }  
  return res;
}

Sorry for my bad English...

Answer 4

I have a (simple) O(n^2 log n) solution which takes into account the fact that i, j and k refer to indices, not integers.

A simple first pass allow us to build an array A of 100 values: values -> list of indices, we keep the list sorted for later use. O(n log n)

For each pair i,j such that i <= j, we compute X = arr[i]^arr[j]. We then perform a binary search in A[X] to locate the number of indices k such that k >= j. O(n^2 log n)

I could not find any way to leverage sorting / counting algorithm because they annihilate the index requirement.

Answer 5

Sort the array, keeping a map of new indices to originals. O(nlgn)
Loop over i,j:i<j. O(n^2)
  Calculate x = arr[i] ^ arr[j]
  Since x ^ arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn)
  For all found k, print mapped i,j,k

O(n^2 lgn)

Answer 6

Start with a frequency count of the number of occurrences of each number between 1 and 100, as Paul suggests. This produces an array freq[] of length 100.

Next, instead of looping over triples A,B,C from that array and testing the condition A^B^C=0, loop over pairs A,B with A < B. For each A,B, calculate C=A^B (so that now A^B^C=0), and verify that A < B < C < 100. (Any triple will occur in some order, so this doesn't miss triples. But see below). The running total will look like:

Sum+=freq[A]*freq[B]*freq[C]

The work is O(n) for the frequency count, plus about 5000 for the loop over A < B.

Since every triple of three different numbers A,B,C must occur in some order, this finds each such triple exactly once. Next you'll have to look for triples in which two numbers are equal. But if two numbers are equal and the xor of three of them is 0, the third number must be zero. So this amounts to a secondary linear search for B over the frequency count array, counting occurrences of (A=0, B=C < 100). (Be very careful with this case, and especially careful with the case B=0. The count is not just freq[B] ** 2 or freq[0] ** 3. There is a little combinatorics problem hiding there.)

Hope this helps!