1 thing i forgot to mention in my above post that at first i will also check max - min + 1 must be equal to n. then only move further else the array will not be consecutive after sort. I think it will give correct output. please tell if any counter example.
On Sat, Jun 25, 2011 at 2:29 AM, pacific :-) <[email protected]> wrote: > My approach : > 1. Find the median. > 1.5 Check if the median is min + (max - min ) / 2. > 2. Partition the array into two sub arrays using the partition function of > quicksort. > 3. Check if the subarrays also satisfy the constraint. > > Complexity : T(n) = 2 T(n/2) + O(1) :: O(nlogn) > > > > > On Sat, Jun 25, 2011 at 12:15 PM, varun pahwa <[email protected]>wrote: > >> will this work. >> n size of array. >> cal (a[i] - min(arr) + 1). >> now cal sum of a[i], cal square sum of array as (a[i] * a[i]) , cal cube >> sum of array as (a[i] * a[i] * a[i]). now if array elements are consecutive >> then sum must be n * (n + 1) / 2. square sum must be (n * (n + 1) * (2n + 1) >> )/ 6 and cube sum must be (n * (n + 1) / 2) ^ 2. >> >> >> >> On Fri, Jun 24, 2011 at 11:00 PM, Adarsh <[email protected]> wrote: >> >>> I think I got an work around for this.... if number of elements are >>> not odd why not make them odd :) >>> I variation to my prev algo >>> >>> int n = A.size(); >>> for (int i=0; i<n; i++) >>> total += A[i]; >>> findMinMax(A[1...n]); //returns first smallest (fmin), second smallest >>> (smin) and largest (max) element in array >>> >>> int fmean = (max+fmin)/2; >>> int smean = (max+smin)/2; >>> stotal = total - fmin; >>> if ((total - n*fmean) == 0) >>> { >>> if ((stotal - n*smean) == 0) >>> printf("consecutive\n"); >>> return; >>> } >>> printf("not consecutive\n"); >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> Varun Pahwa >> B.Tech (IT) >> 7th Sem. >> Indian Institute of Information Technology Allahabad. >> Ph : 09793899112 ,08011820777 >> Official Email :: [email protected] >> Another Email :: [email protected] >> >> People who fail to plan are those who plan to fail. >> >> -- >> 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. >> > > > > -- > regards, > chinna. > > -- > 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. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- 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.
