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 <varunpahwa2...@gmail.com>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 <s.adars...@gmail.com> 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 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.
>>
>>
>
>
> --
> Varun Pahwa
> B.Tech (IT)
> 7th Sem.
> Indian Institute of Information Technology Allahabad.
> Ph : 09793899112 ,08011820777
> Official Email :: rit2008...@iiita.ac.in
> Another Email :: varunpahwa.ii...@gmail.com
>
> 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 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.
>
--
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 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.
