Thursday Code Puzzler: Efficient Duplicate Detection

What should the output of the algorithm be?  The duplicate number and its second position in the array?

Daniel code might be a tad more efficent.

 

 Here's mine in Java too:

 static int getDuplicate(int[] array) {

		final int arraySize = array.length;
		final int arraySizeMinusOne = arraySize - 1;
		final int sumMinusDuplicate = ((arraySizeMinusOne * arraySizeMinusOne) + arraySizeMinusOne) / 2;
		int sum = 0;

		for (int i = 0; i < arraySize; i++) {
			sum += array[i];
		}

Daniel's algorithm in Groovy

def duplicateNumber(numbers) {
	numbers.sum() - (1000 * 1001 / 2)
}
println duplicateNumber(new ArrayList(1..1000).plus(1,10)) //prints 10

Ah.
I had this as an interview question once, after solving it, the interviewer asked me if I could improve it - I couldn't.
Here is what he then showed me:

int numbers[] = {1,2,3,4,5,6,7,8,2,10,11,12,13,14,9}; 

for (int pos = 1; pos < numbers.length; pos++) 
{ 
  numbers[pos] = numbers[pos] ^ numbers[pos-1] ^ pos; 
} 

System.out.println("Duplicate is : " + numbers[numbers.length-1]);  

Good old XOR can be used if it's just numbers, the final result will be in the last position of the array. If you do the bitwise math, it starts making sense, but that's a LOT of 11111111 and 00000000 math!

This algorithm will work here. The algorithm fails for negative numbers.

The algorithm seems to work only if the duplicate is 1. e.g. See code below.

def duplicate(numbers) {
	for (int pos = 1; pos < numbers.length; pos++) 
		numbers[pos] = numbers[pos] ^ numbers[pos-1] ^ pos; 
	numbers[numbers.length - 1]
}
println duplicate([1,2,1,3].toArray())   //prints 1. Right
println duplicate([-1,2,-1,3].toArray()) //prints 1. Wrong.
println duplicate([1000,2,1000,3].toArray()) //prints 1. Wrong.
println duplicate([500,2,500,3].toArray()) //prints 1. Wrong.

println duplicate([250,2,250,3].toArray()) //prints 1. Wrong. 

I prefer Ewald's solution, but of course if will only work if the numbers satisfies the preconditions: "numbers 1 to 1000 inclusive in random order, plus one duplicate number". So if You add negative numbers or skip any of them from the list, it won't :)
Though I guess it could be a bit improved, since we could calculate the XOR-ed value of number 1-1000 (which is 1000 btw) in advance and store it as a constant in the code. Then we just need to XOR all the values in the array, at the end XOR the precalculated constant and voila, the result is the duplicated number.

Hi!

 

I guess this algorithm works for negative numbers as well. You just need a continuous interval of numbers, for example -499 to 500 (The precalculated XOR-ed value for this interval is -8)
The trick is that if You XOR a number with itself the result is 0. Also if You XOR something with 0 the result is not changed. So in Your original solution all the numbers are XOR-ed twice (once from the array of numbers and once as the index), except of course the duplicated number which appear three times. Since pairs "kills" each other the full XOR-ed result is the duplicated number.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
public class EfficientDuplicateDetection {
	public static void main(String[] args) {
		ArrayList randomList = new ArrayList();
		Random randomGen = new Random();
		for(int i=0;i<1001;i++) {
			randomList.add(new Integer(randomGen.nextInt(1000)));
		}
		HashMap duplicateIdentifier = new HashMap();
		int countDuplicate =0;
		for(int i=0;i<1001;i++) {
			Integer listVal = (Integer)randomList.get(i);
			if(duplicateIdentifier.containsKey(listVal)) {
				System.out.println("Duplicate Found " + listVal);
				countDuplicate++;
			} else {
				duplicateIdentifier.put(listVal, listVal);
				//System.out.println(listVal);
			}
		}
		System.out.println("Total Number of Duplicates  " + countDuplicate);
	}
}

A set will be more efficient e.g. Groovy code

def duplicateNumber(numbers) {
	def f = new HashSet()
	numbers.find { !f.add(it) }
}

println duplicateNumber(new ArrayList(1..1000).plus(1,10)) //prints 10 

Vijay, I think your code is correct, but your tests on line 7-9 are incorrect.  A key part of the problem is that the range is continuous. When that is the case there are always pairs of values and positions that will XOR to zero for all but the duplicate.

Hi!
Yes, they can be in random order, but all the numbers for a continuous range should be included. So if You're using numbers from 1 to 10, in Your list You should have 11 numbers: the 10 numbers 1, 2, ... 10 and one duplicate in any order. Your example misses numbers 4, 6, 7, 8, 9, so the algorithm with XORs wont work.

Well, actually - as I've wrote in a previous comment - it even works for negative numbers. You just have to be sure that indexes goes through the same range as randomly ordered numbers. So at the end each number appears twice: once from the list of randomly ordered numbers and once from the index. Except of course the duplicated number which appears three times and therefore remains at the end.