Issue:
a array stores N data with range from 1 to N-1, please write a function with time complexity O(N) to print out the duplicated data in array.
e.g.
int ary[10] = {1,2,3,4,5,6,7,7,9,0};
duplicated(ary, 10); // print out 7
And here is my implementation with TC O(N) and space complexity O(1);
1 int duplicated(int a[], int N)
2 {
3 int i = 0, ai;
4 while(i<N) {
5 ai = a[i];
6 if(ai == i) i++;
7 else if(ai != a[ai]) {
8 a[i] ^= a[ai];
9 a[ai] ^= a[i];
10 a[i] ^= a[ai];
11 }
12 else return a[i];
13 }
14 return -1;
15 }
16
17 char duplicated_char(char a[], int N)
18 {
19 int i = 0, ai;
20 while(i<N) {
21 ai = a[i]-'a';
22 if(a[i] == i+'a') i++;
23 else if(a[i] != a[ai]) {
24 a[i] ^= a[ai];
25 a[ai] ^= a[i];
26 a[i] ^= a[ai];
27 }
28 else return a[i];
29 }
30 return -1;
31 }