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+c b+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 gives b-a = 2
a[0] is b+a=4
that gives b=3,a=1
Now u have a and b calculate c as a[1]-a=4
and d as9 . For this we traverse from a[1] to a[N-2]
We calculate a and b because we know the order of sum of their
elements(a+bis given and b's addition with rest elements are there in
array)
This will work in Linear Time
Now lets take an example with 8 elements to
let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8
then N=8 and array is
3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15
Now by above logic first
a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36
Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5
a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1
Now we have a=1,b=2
So we traverse from a[1] to a[N-2] to calculate values c to h
c= a[1]-a=4-1=3
d=a[2]-a=5-1=4
e=a[3]-a=6-1=5
similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8
This will work in O(n)
Regards
Ankur
On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank <[email protected]>wrote:
> @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 Mesra
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/lF0kSVRUp5cJ.
>
> 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.
