Find the missing and duplicate elements in an array in linear time and constant space

by

If all numbers were present in the array the sum would be N(N+1)/2.

Determine the actual sum by summing up all numbers in the array in O(n), let this be Sum(Actual).

One number is missing, let this be j and one number is duplicated, let this be k. That means that

Sum(Actual) = N(N+1)/2 + k – j

derived from that

k = Sum(Actual) -N(N+1)/2 + j

Also we can calculate the sum of squares in the array, which would sum up to
n3/3 + n2/2 + n/6 if all numbers were present.

Now we can calculate the actual sum of squares in O(n), let this be Sum(Actual Squares).

Sum(Actual Squares) =n3/3 +
n2/2 + n/6 + k2
– j2

Now we have two equations with which we can determine j and k.

More Related Contents:

  1. How can I pair socks from a pile efficiently?
  2. Unique (non-repeating) random numbers in O(1)?
  3. What is tail call optimization?
  4. What distribution do you get from this broken random shuffle?
  5. How do I check if a number is a palindrome?
  6. Is there an O(n) integer sorting algorithm?
  7. Data structures for loaded dice?
  8. Determine font color based on background color
  9. Nearest neighbors in high-dimensional data?
  10. Algorithm to generate anagrams
  11. Generate all unique substrings for given string
  12. design a stack such that getMinimum( ) should be O(1)
  13. How to check if line segment intersects a rectangle?
  14. How to read values from numbers written as words?
  15. Calculate largest inscribed rectangle in a rotated rectangle
  16. Find the first un-repeated character in a string
  17. The Sieve of Atkin
  18. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  19. 3 dimensional bin packing algorithms
  20. What is a bubble sort good for? [closed]
  21. Iterating over a Binary Tree with O(1) Auxiliary Space
  22. How do I find a factorial? [closed]
  23. Best way of calculating n choose k?
  24. Peak detection of measured signal
  25. “Rounding” colour values to the nearest of a small set of colours
  26. Algorithm for permutations of operators and operands
  27. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  28. Tournament bracket placement algorithm
  29. How to convert decimal fractions to hexadecimal fractions?
  30. Best algorithm for matching colours.

Leave a Comment