Your algorithm is good, but the first part doesn't help you because duplicates are allowed.
Here is code that does what you say: #include <stdio.h> int main(void) { int a[] = { 6, 2, 4, 8, 7, 3, 5 }; int n = sizeof a / sizeof a[0]; int i, t, min, max, tmp; min = max = a[0]; for (i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } if (min + n - 1 != max) { printf("no\n"); return 1; } for (i = 0; i < n; i++) { while (a[i] != i + min) { t = a[a[i] - min]; if (t == a[i]) { printf("no\n"); return 1; } a[a[i] - min] = a[i]; a[i] = t; } } for (i = 0; i < n; i++) printf("%d ", a[i]); printf("yes\n"); return 0; } On Jun 25, 11:22 pm, "oppilas ." <jatka.oppimi...@gmail.com> wrote: > Divye Thanks for the link. > Quoting the top answer from there. > > "Under the assumption numbers less than one are not allowed and there > are no duplicates, there is a simple summation identity for this - the > sum of numbers from 1 to m in increments of 1 is (m * (m + 1)) / 2. > You can then sum the array and use this identity. > > You can find out if there is a dupe under the above guarantees, plus > the guarantee no number is above m or less than n (which can be > checked in O(N)) > > The idea in pseudo-code: > 0) Start at N = 0 > 1) Take the N-th element in the list. > 2) If it is not in the right place if the list had been sorted, check > where it should be. > 3) If the place where it should be already has the same number, you > have a dupe - RETURN TRUE > 4) Otherwise, swap the numbers (to put the first number in the right place). > 5) With the number you just swapped with, is it in the right place? > 6) If no, go back to step two. > 7) Otherwise, start at step one with N = N + 1. If this would be past > the end of the list, you have no dupes. > > And, yes, that runs in O(N) although it may look like O(N ^ 2) > " > > On 6/26/11, DK <divyekap...@gmail.com> wrote: > > > > > @Chinna: Your algorithm is simple quicksort with partition selection using > > medians. O(n log n) worst case. > > @Varun: You cannot prove that your algorithm will work for all cases. Hence, > > claiming a worst case bound of O(n) is incorrect. > > >http://stackoverflow.mobi/question177118_Algorithm-to-determine-if-ar... > > > -- > > DK > > >http://twitter.com/divyekapoor > >http://www.divye.in > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To view this discussion on the web visit > >https://groups.google.com/d/msg/algogeeks/-/rRP-R-G2MM4J. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.