CareerCup

Since there is only 1 number without a pair, the array size is always odd. We can start with the middle. If the middle number is different from its neighbors, it's the number without the pair.

Here is the code I come up with in C#.

int printDuplicate(int[] array, int size)
{
	int half = size / 2;
	size = half;
	while (true)
	{
		if (array[half] != array[half-1] && array[half] != array[half+1]
		{
			Console.WriteLine(array[half]);
			break;
		}
		else if (array[half] != array[half+1])
		{
			// Check Left
			half = size / 2 - 1;
		}
		else
		{
			// Check Right
			half = size + (size / 2 + 1);
		}
		
		size = size / 2 - 1;
	}
}

this can be solved in O(n) and with no additional memory

public int find (int [] array){
		int n = 0 ;
		for (int v : array) {
			n ^= v ;
		}
		return n ;
	}

Yeah, after looking around I saw the xor solution. Looking at mine it looks like my worst cast solution isn't actually n log n, it's n/2 in the worst case because I am jumping over each paired item so only needing to check half the elements.

I still don't see why they were pushing a BST or binary search solution.

You can get your answer in O(log n) time using binary search. Because all numbers except one come in pairs, you can divide the whole range in half, and then deduce the half your unique number belongs to. Here's C# code for that:

static int FindUnique(int[] values)
        {
            int pairCount = values.Length / 2 + 1;
            return FindUnique(values, 0, pairCount - 1);
        }

        static int FindUnique(int[] values, int l, int r)
        {
            if (l == r)
                return values[l * 2];
            int m = l + (r - l) / 2;

            if (values[m * 2] == values[m * 2 + 1] )
                return FindUnique(values, m + 1, r);
            else
                return FindUnique(values, l, m);
        }

use Data::Dumper;
@pairs= (1,1,7,7,3,3,4,19,19,10,10,11,11,15,15,2,2);
my %help;
map {$help{$_}++} @pairs;
@a = keys %help;
print @a;
print Dumper \%help;

/**
 * Created by tiwariaa on 6/30/15.
 */
public class NonDuplicate {
    static int pairs[] = {1, 1, 7, 7,8,8,99,99, 3, 3, 19, 19, 4, 10, 10, 11, 11, 15, 15, 2, 2};
    static int index = 0;
    public static boolean findDublicate(int lastNo, boolean flag){
        if(pairs.length - 1 == index || flag){
            return true;
        }
        index++;
        if(index !=0 && index % 2 == 0){
            return findDublicate(pairs[index], false);
        }else{
            if(lastNo != pairs[index])
                return true;
            return findDublicate(pairs[index], false);
        }
    }
    public static void main(String[] ate) {
        findDublicate(pairs[index], false);
        System.out.println("---------->" + pairs[index -1]);
    }
}

Ruby impl. Running time: O(n). Space: O(1).

def find_non_dup(array)
  return nil if !array.kind_of?(Array) || array.length <= 1
  
  iter=1
  
  while iter<array.length
    if array[iter] != array[iter-1]
      return array[iter-1]
    else
      iter+=2;
    end
  end
    
end

If you pick the middle element and it doesn't equal either of it's neighbors, you're done. Otherwise, recurse into the odd half the array.