I saw this term "non-decreasing order"
So we need to sort the numbers first..it will take nlogn .
On Fri, Dec 16, 2011 at 1:12 AM, Ankur Garg wrote:
> on above algo , there is no need to calculate sum of array so we can do it
> in O(N) and not O(n).
>
>
> On Fri, Dec 16, 2011 at 12:59 AM, Ankur
on above algo , there is no need to calculate sum of array so we can do it
in O(N) and not O(n).
On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg wrote:
> Hi Topcoder.
>
> First of all you posted the wrong array .
>
> The array should be
>
> 4, 5, 10, 7, 12, 13
> a+b a+c
Hi Topcoder.
First of all you posted the wrong array .
The array should be
4, 5, 10, 7, 12, 13
a+b a+c a+d b+cb+d c+d
Now first calculate a+b+c+d which will be (sumofarray)/N-1
So here a+b+c+d = 17
Now take a[1] is a+c
and a[N-1] = b+c
subtracting them giv
@all , a Naive Approach with Quadratic Time will be for each i=1 to n ,
check if i and a[i]-i makes given sum , so for each each number we will do
the thus can achieve the solution ...i am just thinking about if we can do
it linear time ..will post if able to do it :)
Thanks
Shashank
CSe BIT M