If the range is (0,n) then we can solve in O(n) TC and O(1) SC.
int checkconsequtive(int a[],int n){
if(n<1)
return 0;
int min=a[0];
int max=a[0];
int i=0;
for(i=1;i<n;i++)
{
if(a[i]<min)
min=a[i];
if(a[i]>max)
max=a[i];
}
if(max-min+1!=n)
return 0;
for(i=0;i<n;i++)
{
if(a[a[i]-min]<0)
return 0;
a[a[i]-min]=-a[a[i]-min];
}
for(i=0;i<n;i++)
a[i]=-a[i];
return 1;}
On Wed, Jul 6, 2011 at 3:46 PM, Gaurav Tyagi <cho...@gmail.com> wrote:
>
> a) Find min(A). - O(n)
> b) Find max(A) - O(n)
> c) Calculate sum of natural numbers starting from min(A) to max(A) -
> O(n)
> d) Calculate sum of all numbers in the array. - O(n)
> e) If sum in step c) is not same as sum in step d), then elements are
> not consecutive. If the sum is same, then they are consecutive.
>
> Can anyone think of a counterexample that breaks the above algo.
>
> On Jul 6, 8:25 am, Sathaiah Dontula <don.sat...@gmail.com> wrote:
> > How about doing like this ?.
> >
> > Without loss of generality, I can assume that numbers starts from 1
> > (if not, if it starts from ZERO, add by 1 to all the numbers,
> > if it is negative, find the min value, assume it is X, add by (-X)+1))
> >
> > Now assume numbers are M, compute the product of the numbers and compute
> M!
> > and check if they are equal.
> >
> > does it work ?
> >
> > Thanks,
> > Sathaiah
> >
> > On Wed, Jul 6, 2011 at 11:45 AM, Anantha Krishnan <
> >
> >
> >
> >
> >
> >
> >
> > ananthakrishnan....@gmail.com> wrote:
> > > Check this
> >
> > > *int isconsecutive(int a[], int n) {*
> > > * if (n < 1) {*
> > > * return 0;*
> > > * }*
> > > * int max = a[0], min = a[0];*
> > > * int i = 0;*
> > > *
> > > *
> > > * int *hash = (int*) calloc(n, sizeof (int));*
> > > *
> > > *
> > > * //find min and max from the array*
> > > * for (i = 1; i < n; i++) {*
> > > * if (a[i] < min)*
> > > * min = a[i];*
> > > * else if (a[i] > max)*
> > > * max = a[i];*
> > > * }*
> > > *
> > > *
> > > * if (max - min + 1 != n)*
> > > * return 0;*
> > > *
> > > *
> > > * for (i = 0; i < n; i++) {*
> > > * if (hash[a[i] - min + 1] == 1)*
> > > * return 0;*
> > > * hash[a[i] - min + 1] = 1;*
> > > * }*
> > > * return 1;*
> > > *
> > > *
> > > *}*
> > > *
> > > *
> > > *int main(int argc, char** argv) {*
> > > *
> > > *
> > > * int a[] = {-1, 0,1,2, 4, 3, 5};*
> > > * int n = sizeof (a) / sizeof (a[0]);*
> > > * printf("%d", isconsecutive(a, n));*
> > > *
> > > *
> > > * return (EXIT_SUCCESS);*
> > > *}*
> >
> > > On Sat, Jun 25, 2011 at 1:14 AM, ross <jagadish1...@gmail.com> 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 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.
> >
> > > --
> > > 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.
>
> --
> 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.
>
>
--
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.
