Advertisement
bigyan

Duplicates in linear time

Apr 21st, 2011
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.97 KB | None | 0 0
  1. /*
  2. http://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space
  3.  
  4. Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.
  5.  
  6. Goal : To find these repeating numbers in O(n) and using only constant memory space.
  7.  
  8. For example, let n be 7 and array be {1, 2, 3, 1, 3, 0, 6}, the answer should be 1 & 3. I checked similar questions here but the answers used some data structures like HashSet etc.
  9.  
  10. Any efficient algorithm for the same?
  11. */
  12.  
  13.  
  14. #include <stdio.h>
  15.  
  16. void dupes(int a[], int n)
  17. {
  18.     int i;
  19.  
  20.     for (i = 0; i < n; i++)
  21.         while (a[a[i]] != a[i]) {
  22.             int tmp = a[i];
  23.             a[i] = a[tmp];
  24.             a[tmp] = tmp;
  25.         }
  26.  
  27.     for (i = 0; i < n; i++)
  28.         if (a[i] != i)
  29.             printf("%d ", a[i]);
  30.  
  31.     printf("\n");
  32. }
  33.  
  34. int main()
  35. {
  36.     int x[] = {0, 6, 2, 3, 4, 5, 2};
  37.  
  38.     dupes(x, sizeof x / sizeof x[0]);
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement