I have a solution that will do the job in O(n) time but will require three
variables....but this solution won't work if the array contains -ve numbers.
*
int findrepeat(int a[],int n)
{
int i,xor = 0;
int min = findmin(a,n);
int max = findmax(a,n);
if((max-min+1)!=n)
return 0;
for(i = 0 ;i<n;i++)
xor^=a[i];
for(i=min;i<=max;i++)
xor^=i;
if(xor)
return 0;
else
return 1;
}*
Please let me know if there is any counter example..
On Sat, Jun 25, 2011 at 1:17 AM, ross <[email protected]> wrote:
> One solution would be to : check if max-min = N and
> that all elements are unique in the array.
> However, this may require space complexity.. Looking for a
> better solution.
>
> On Jun 25, 12:44 am, ross <[email protected]> wrote:
> > Given an array, A, find if all elements in the sorted version of A are
> > consecutive in less than O(nlogn).
> > eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive --
> > true
> > A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive -
> > false
>
> --
> 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.
>
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
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.
