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 <ankurga...@gmail.com> 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 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 > <shashank7andr...@gmail.com>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 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. >> > > -- 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.
