psuedo code to find repeating number?

Question

Array has total 101 values. This array contains numbers from 1 to 100 and one number is repeating (two times). Write psuedo code to find repeating number.

Answer 1

1. You could hash the values and detect collisions
2. You could sort the array then loop it finding duplicates
3. You could search the array (long and slow!)

If you want to be smart, take a look at hashing. If you want to play it easy and safe, sorting the list with merge sort then looping the indexes would probably be best.

Answer 2

I'd add up all the indexes [0] -> [100] find out what 1 + 2 + 3 ... + 100 should equal subtract that from your result and you got the repeating number.

So you'd just have a simple

for or while loop going through each index then subtract the 2 and you have your result.

Something like...

q = 0;
p = 101 * 50;
for(i<=100; i <array.length; i++){
 q += q + array[i]
 }
 repeating number = q-p;

Answer 3

Try this (C#):

int[] array = ... ; // initialize appropriately
var hashSet = new HashSet<int>();
var indexOfDuplicate = -1;
for (var i = 0; i < array.Length; i++) {
   if (hashSet.Contains(array[i])) {
      indexOfDuplicate = i;
      break;
   }
   hashSet.Add(array[i]);
}
var duplicateNumber = array[indexOfDuplicate];

With this solution you will have both the index of the duplicate number (2nd occurrence) and the duplicate number.

Answer 4

Set set;

for each p in array { set.add(p); }

print(set);