can't we directly hash the values at a[i] % N, if value is Negative hash to
(A[i]%N) + N
if two values hash to same places -----Not consecutive
But still we can have a problem like
N = 2 and a[] = {1,4}
because of hash value of values in the array may be consecutive but not the
actual values
so after hashing we need a final check
whether the values are actually consecutive.
to check this we only need to find if the array is a rotated sorted array
with all values with difference 1
and at rotation difference will be equal to N-1
like array {-3, -1, 3, 2, 1, 0 -2} will hash to {0, 1, 2, 3, -3, -2, -1}
On Wed, Jun 29, 2011 at 2:22 PM, 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)
>
>
>
>
>
> --
> 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.
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
