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.