Finding duplicates in O(n) time and O(1) space

by

This is what I came up with, which doesn’t require the additional sign bit:

for i := 0 to n - 1
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 0 to n - 1
    if A[i] != i then 
        print A[i]
    end if
end for

The first loop permutes the array so that if element x is present at least once, then one of those entries will be at position A[x].

Note that it may not look O(n) at first blush, but it is – although it has a nested loop, it still runs in O(N) time. A swap only occurs if there is an i such that A[i] != i, and each swap sets at least one element such that A[i] == i, where that wasn’t true before. This means that the total number of swaps (and thus the total number of executions of the while loop body) is at most N-1.

The second loop prints the values of x for which A[x] doesn’t equal x – since the first loop guarantees that if x exists at least once in the array, one of those instances will be at A[x], this means that it prints those values of x which are not present in the array.

(Ideone link so you can play with it)

More Related Contents:

  1. How to find number of words in a phrase with spaces removed by checking v. dictionary
  2. Program stopped working, when tried to run
  3. Absolute Distinct Numbers
  4. C++ throwing exception in recursive algorithm
  5. How to use Quick Sort to sort an array of strings
  6. How to get the maximum number after erasing n digits from the number [closed]
  7. Calculating pow(a,b) mod n
  8. Fast exact bigint factorial
  9. Generating combinations in c++
  10. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  11. Lock-free Progress Guarantees in a circular buffer queue
  12. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  13. Emulate “double” using 2 “float”s
  14. LRU cache design
  15. Need for predictable random generator
  16. Determining if a number is prime
  17. How to add two numbers without using ++ or + or another arithmetic operator
  18. Are there any better methods to do permutation of string?
  19. Iterative DFS vs Recursive DFS and different elements order
  20. Converting epoch time to “real” date/time
  21. Searching in a sorted and rotated array
  22. `std::list::sort()` – why the sudden switch to top-down strategy?
  23. How can I sort an STL map by value?
  24. Easiest way of using min priority queue with key update in C++
  25. What is the safe way to fill multidimensional array using std::fill?
  26. Edges on polygon outlines not always correct
  27. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  28. Why there is no std::copy_if algorithm?
  29. LRU implementation in production code
  30. How can I test whether a number is a power of 2?

Leave a Comment