Re: [algogeeks] Re: find numbers if pair wise sums are given
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 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.comwrote: @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.
Re: [algogeeks] Re: find numbers if pair wise sums are given
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+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 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.comwrote: @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.
Re: [algogeeks] Re: find numbers if pair wise sums are given
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+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 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.
[algogeeks] Re: find numbers if pair wise sums are given
@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.
