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