-3

Given an array whose elements are consecutive distinct elements except one which is duplicate, I need to find the most efficient way to find the duplicate element. I was thinking of just scanning through the array and checking if array[i+1] is greater than array[i]. If it is not then duplicate found. But is there a better solution. Also, using my algorithm you wouldn't know whether to array[i+1] or array[i] is the duplicate element.

user37375
  • 173
  • 1
  • 5
  • 22
  • What is the type? Consecutive **what**? – PM 77-1 Mar 29 '15 at 01:24
  • Consecutive integers – user37375 Mar 29 '15 at 01:25
  • Code your best try up and post an example. Or try them both. Show us the code and where you're stuck if it doesn't work. – clearlight Mar 29 '15 at 01:25
  • What do you need to find: its value, position, or both? – PM 77-1 Mar 29 '15 at 01:26
  • Okay, does the solution I described work? – user37375 Mar 29 '15 at 01:26
  • @user37375 Why don't you try? – Erwin Bolwidt Mar 29 '15 at 01:27
  • @PM77-1 I need to find the duplicate element value – user37375 Mar 29 '15 at 01:27
  • @ErwinBolwidt Sorry, I was wondering if the solution I described is the most efficient – user37375 Mar 29 '15 at 01:29
  • Then please edit your answer and rephrase the question. – clearlight Mar 29 '15 at 01:29
  • @I.K. not a duplicate, as the array has consecutive elements in this case. I think we need to use that fact to figure out which element is duplicate – user37375 Mar 29 '15 at 01:34
  • Your solution assumes the array is sorted, which is not in the problem statement. So I'm sorry you muffed the interview. It only says the elements are consecutive, so I assume that means they're integers and further that they're non-negative. In this case you can find an answer in linear time and constant space because the sum of consecutive integers from A to B is B(B+1)/2-A(A+1)/2. So just make a pass over the array to find min=A, max=B, and sum, then the duplicate element is sum-(B(B+1)/2-A(A+1)/2). A similar but slightly more complicated solution is possible if the numbers can be negative. – Gene Mar 29 '15 at 02:04
  • Making one complete pass over the array to sum the elements is less efficient than OP's original solution since by traversing once the duplicate can be found without summing and *possibly* without having to traverse the whole array. –  Mar 29 '15 at 02:10
  • @I.K. As I said, there is nothing in the problem statement that says the array is sorted. – Gene Mar 29 '15 at 04:48
  • @Gene Thanks for the solution Gene! :D It was helpful! But where did u come up with the formula of B(B+1)/2-A(A+1)/2? – user37375 Mar 29 '15 at 07:19

1 Answers1

0

Something like that (if the elements are type String and your array is called yourArray):

HashSet<String> set = new HashSet<String>();

    for (String elem : yourArray)
    {
        if(!set.add(elem))
        {
            System.out.println(elem); //or whatever you want to do here
        }
    }
b10n1k
  • 567
  • 5
  • 21