I was responding to oppilas. His use of the formula N(N+1)/2 really doesn't help here. Hashing will work fine, but it's not the simplest or most efficient way. Because you're testing for consecutive integers, it makes more sense to use an array(min .. max) of booleans to test for duplicates rather than a hash table. Set them all false and then go through the data setting the corresponding boolean true for each. If you are about to set one true and it's already set, you have a duplicate.
The algorithm of oppilas cleverly substitutes a special ordering of the original array for the array of booleans above. Swapping the i'th largest integer to the i'th array position is the same as setting the boolean true. If you are about to swap a value into an array position that already contains that value, you have a duplicate. On Jun 29, 4:52 am, Aakash Johari <[email protected]> wrote: > Please read it again. Hashing would also help in the case of duplicates. > > > > > > On Wed, Jun 29, 2011 at 9:16 AM, Gene <[email protected]> wrote: > > 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 ." <[email protected]> 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 <[email protected]> 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 [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]. > > > > 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 [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > -Aakash Johari > (IIIT Allahabad)- 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
