Most efficient way - Interview C++

So it goes like this:

You have a ordered array. All elements only repeat once but one of them repeats twice. Find the most efficient way(time complexity wise) to find which element repeats twice.


1 2 4 6 8 8 9

For this the program would return 8, because 8 is the number that repeats twice. Any ideas? Any help is appreciated.

1 answer

  • answered 2018-01-16 14:26 S-Wing

    The most easy way is something like (you havn't specified any particoular language):

    for(int i = 0; i<array.length-1;i++){
       if (array[i] == array[i+1])
           return array[i];

    But I don't think this is the most efficient way