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 <[email protected]> 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 < > > > > > > > > [email protected]> 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 <[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. > > > -- > > 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. -- 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.
