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.
