Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- http://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space
- 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.
- Goal : To find these repeating numbers in O(n) and using only constant memory space.
- 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.
- Any efficient algorithm for the same?
- */
- #include <stdio.h>
- void dupes(int a[], int n)
- {
- int i;
- for (i = 0; i < n; i++)
- while (a[a[i]] != a[i]) {
- int tmp = a[i];
- a[i] = a[tmp];
- a[tmp] = tmp;
- }
- for (i = 0; i < n; i++)
- if (a[i] != i)
- printf("%d ", a[i]);
- printf("\n");
- }
- int main()
- {
- int x[] = {0, 6, 2, 3, 4, 5, 2};
- dupes(x, sizeof x / sizeof x[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement