0

If I have an array of n length of unique values except one that is duplicated, what is the quickest way to find it?

e.g. [1, 2, 3, 4, 4, 10, 15, 12] quickest way to find that it is a 4. There could be millions of array elements.

alexrogers
  • 1,514
  • 1
  • 16
  • 27
  • 1
    This is the third time I've seen this question in the last week. Where are you people interviewing? http://stackoverflow.com/questions/26995607/find-unique-elements-from-sorted-array-with-complexity-on#comment42521929_26995607 – vz0 Nov 26 '14 at 10:46
  • Your example array is sorted. Is that always going to be the case? Is there always only one duplicate? – Jongware Nov 26 '14 at 10:47
  • possible duplicate of [Finding unique numbers from sorted array in less than O(n)](http://stackoverflow.com/questions/26958118/finding-unique-numbers-from-sorted-array-in-less-than-on) – Jongware Nov 26 '14 at 10:48
  • **unique** <-> **repeated** ? – Yu Hao Nov 26 '14 at 10:48
  • Is there always only one duplicate? Yes Your example array is sorted - no it isn't - sorry isn't the best example but still works – alexrogers Nov 27 '14 at 10:16
  • Also @vz0 that isn't the same question – alexrogers Nov 27 '14 at 10:17

3 Answers3

1

If you have feasibility to use Data Structure you can do it in CONSTANT time. i.e approx O(1). That is using a HashMap. (when we are dealing with millions of numbers)

You can also use a separate array say (Dummy) of size of max(element present in array) and then go on putting the element in the Dummy[element] and wherever you find the element is already present you achieve the desired result. It will also take O(n) complexity.

Prakhar Asthana
  • 91
  • 5
1

You have to go through all the elements of the array, one by one. Without more information there is no way to locate the repeated element without touching at least once each element. This is at least O(N) and you can't go faster.

If the repeated elements are consecutive, for example [1,2,2,3], you can go one by one and compare it to the previous one; if they are equal you've found your element:

for (int i = 1; i < count; i++) {
  if (arr[i] == arr[i-1]) {
    std::cout << "found " << arr[i] << " at " << i << " and " << (i-1) << std::endl;
    break;
  }
}

If the repeated elements are not consecutive you can use a data structure to keep track of existing elements. When you find an element which has already been seen you inform that element:

initialize set to empty set;
for (i = 0; i < count; i++) {
  if (arr[i] is in set) {
    inform arr[i] as repeated element at position i;
    break;
  } else {
    add arr[i] to set;
  }
}
vz0
  • 32,345
  • 7
  • 44
  • 77
0

If the duplicate is in a completely random place, I don't see anyway around checking 1 by 1 until you find the duplicate at which point you would obviously stop.

Spaceship09
  • 341
  • 3
  • 8