Problem: given a long sequence of numbers, find those *two* that have odd number of occurrences. Limitations: * the sequence can be traversed only once * 10 KB of memory

gistfile1.cs

/*
Problem: given a long sequence of numbers, find those *two* that have odd number of occurrences. 
 
Limitations: 
* the sequence can be traversed only once 
* 10 KB of memory
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    class Program
    {
        struct Xored
        {
            public long odd;
            public long even;
        }

        static void findThem(IEnumerable<long> input, out long first, out long second)
        {
            const int limit = 64;
            Xored[] xors = new Xored[limit];
            int zeroOcc = 0;

            foreach (int x in input)
            {
                if (x == 0)
                {
                    zeroOcc++;
                    continue;
                }

                int shifted = x;
                for (int offset = 0; offset < limit; offset++)
                {
                    if (shifted % 2 == 0)
                    {
                        xors[offset].even ^= x;
                    }
                    else
                    {
                        xors[offset].odd ^= x;
                    }

                    shifted /= 2;
                }
            }

            if (zeroOcc % 2 != 0)
            {
                first = 0;
                Debug.Assert(xors[0].even == 0 || xors[0].odd == 0);
                second = xors[0].even + xors[0].odd;
                return;
            }

            foreach (Xored xored in xors)
            {
                if (xored.even != 0 && xored.odd != 0)
                {
                    first = xored.even;
                    second = xored.odd;
                    return;
                }
            }

            throw new ArgumentException("Didn't find");
        }

        // not the best, but hey..
        static IEnumerable<long> generateInput(int max, long first, long second)
        {
            int[] occur = new int[max];
            Random rand = new Random();

            for (int i = 0; i < max; i++)
            {
                long x = rand.Next(max);
                occur[x]++;
                yield return x;
            }

            for (int x = 0; x < max; x++)
            {
                int min = x == first || x == second ? 1 : 0;
                if (min == 1 && occur[x] == 0)
                {
                    yield return x;
                    continue;
                }

                while (occur[x] > min)
                {
                    yield return x;
                    occur[x]--;
                }
            }

        }
        static void Main(string[] args)
        {
            Random rand = new Random();
            const int testCount = 100;
            for (int testCase = 0; testCase < testCount; testCase++)
            {
                const int max = 100;
                long expectedFirst = rand.Next(max);
                long expectedSecond;
                do
                {
                    expectedSecond = rand.Next(max);
                } while (expectedFirst == expectedSecond);

                long actualFirst, actualSecond;

                var input = generateInput(max, expectedFirst, expectedSecond);
                findThem(input, out actualFirst, out actualSecond);
                if (actualFirst == expectedFirst && actualSecond == expectedSecond
                    || actualFirst == expectedSecond && actualSecond == expectedFirst)
                {
                    Console.WriteLine("{0}/{1}", testCase + 1, testCount);
                }
                else
                {
                    Console.WriteLine("Fail");
                    break;
                }
            }
        }
    }
}