Please read it again. Hashing would also help in the case of duplicates.
On Wed, Jun 29, 2011 at 9:16 AM, Gene <gene.ress...@gmail.com> 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 ." <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.
>
>
--
-Aakash Johari
(IIIT Allahabad)
--
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.
