Find duplicate element in array in time O(n)

by

This can be done in O(n) time and O(1) space.

(The algorithm only works because the numbers are consecutive integers in a known range):

In a single pass through the vector, compute the sum of all the numbers, and the sum of the squares of all the numbers.

Subtract the sum of all the numbers from N(N-1)/2. Call this A.

Subtract the sum of the squares from N(N-1)(2N-1)/6. Divide this by A. Call the result B.

The number which was removed is (B + A)/2 and the number it was replaced with is (B - A)/2.

Example:

The vector is [0, 1, 1, 2, 3, 5]:

  • N = 6

  • Sum of the vector is 0 + 1 + 1 + 2 + 3 + 5 = 12. N(N-1)/2 is 15. A = 3.

  • Sum of the squares is 0 + 1 + 1 + 4 + 9 + 25 = 40. N(N-1)(2N-1)/6 is 55. B = (55 – 40)/A = 5.

  • The number which was removed is (5 + 3) / 2 = 4.

  • The number it was replaced by is (5 – 3) / 2 = 1.

Why it works:

  • The sum of the original vector [0, ..., N-1] is N(N-1)/2. Suppose the value a was removed and replaced by b. Now the sum of the modified vector will be N(N-1)/2 + b - a. If we subtract the sum of the modified vector from N(N-1)/2 we get a - b. So A = a - b.

  • Similarly, the sum of the squares of the original vector is N(N-1)(2N-1)/6. The sum of the squares of the modified vector is N(N-1)(2N-1)/6 + b2 - a2. Subtracting the sum of the squares of the modified vector from the original sum gives a2 - b2, which is the same as (a+b)(a-b). So if we divide it by a - b (i.e., A), we get B = a + b.

  • Now B + A = a + b + a - b = 2a and B - A = a + b - (a - b) = 2b.

More Related Contents:

  1. How to remove repetition in output results in this code
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Finding the max/min value in an array of primitives using Java
  4. Connect 4 check for a win algorithm
  5. Quickest way to find missing number in an array of numbers
  6. Finding the second highest number in array
  7. Java, find intersection of two arrays
  8. Java, Shifting Elements in an Array
  9. All possible combinations of an array
  10. Flatten nested arrays in java
  11. How to find the only number in an array that doesn’t occur twice [duplicate]
  12. Generate Random Numbers in Array [duplicate]
  13. find an element in a sorted matrix [duplicate]
  14. Interview question – Search in sorted array X for index i such that X[i] = i
  15. Random Number Algorithm – Implementation in Java
  16. JAVA ArrayIndexoutofBoundException issue
  17. How to check if an integer is in a set of given ranges? [closed]
  18. How to split a String by space
  19. How to return an array from JNI to Java?
  20. How do I fill arrays in Java?
  21. How does the Java array argument declaration syntax “…” work?
  22. java indexof(String str) method complexity [duplicate]
  23. How to clone a multidimensional array in java? [duplicate]
  24. A better algorithm to find the next palindrome of a number string
  25. Anagram algorithm in java
  26. How do I get the intersection between two arrays as a new array?
  27. Why can I edit the contents of a final array in Java?
  28. How to manipulate arrays. Find the average. Beginner Java
  29. How to deep copy an irregular 2D array
  30. Why does array indexing in Java start with 0?

Leave a Comment