@Dave I tried to run your algorithm but I am not getting the desired results
Taking inputs as given by @coolfrog A B 1 6 3 7 6 9 I am getting A B Sum 1 6 7 3 6 9 6 6 12 9 6 15 and the desired output would have been 1 6 7 1 7 8 3 6 9 1 9 10 6 6 12 I think we are not covering the point where index is reused. If we increment the index by one the the condition like 1 7 8 will not occur. Please suggest. Amod On Oct 16, 5:51 pm, Dave <dave_and_da...@juno.com> wrote: > @Coolfrog$: > > 1. No. It should be O(n + k log k) because finding the kth smallest > element of an array of size n is O(n), using the Median of Medians > algorithm; > seehttp://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selectio.... > > 2. Assuming that the entries in A are distinct and so are the entries > in B, we can handle the equality of sums case: > > find the smallest k elements of A and sort them into ascending order. > find the smallest k elements of B and sort them into ascending order. > ia = 1 > ib = 1 > output ia, ib, A(ia)+B(ib) > for n = 1 to k do > if A(ia + 1) + B(ib) > A(ia) + B(ib + 1) then > ia = ia + 1 > output ia, ib, A(ia)+B(ib) > else if A(ia + 1) + B(ib) < A(ia) + B(ib + 1) then > ib = ib + 1 > output ia, ib, A(ia)+B(ib) > else // equality case > ia = ia + 1 > ib = ib + 1 > output ia-1, ib, A(ia-1)+B(ib) > output ia, ib-1, A(ia)+B(ib-1) > end if > end for > > Dave > > On Oct 16, 6:20 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com> > wrote: > > > > > @Dave > > 1. should it not be O(k + klogk) ?? > > 2. but u are not considering all the possible values... let k =3 > > like i. a1+b1 > > ii. min( a1+b2, a2+b1) upto these fine one of them will be > > chosen ...either ia or ib will increase. > > iii. but know we have to take remaining of step ii in to > > consideration along with > > a1+b3,a3+b1,a2+b3,a3+b2 ... > > > On Fri, Oct 15, 2010 at 8:20 PM, Dave <dave_and_da...@juno.com> wrote: > > > @Coolfrog$: You don't have to sort the arrays. You only have to find > > > the k smallest elements in each and sort those k entries. This can be > > > done in O(n + k log k). > > > > Algorithm: > > > find the smallest k elements of A and sort them into ascending order. > > > find the smallest k elements of B and sort them into ascending order. > > > ia = 1 > > > ib = 1 > > > output ia, ib, A(ia)+B(ib) > > > for n = 1 to k do > > > if A(ia + 1) + B(ib) > A(ia) + B(ib + 1) then > > > ia = ia + 1 > > > else > > > ib = ib + 1 > > > end if > > > output ia, ib, A(ia)+B(ib) > > > end for > > > > Complexity O(n + k log k). > > > > Dave > > > > On Oct 15, 4:00 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com> > > > wrote: > > > > @amod > > > > as given A->B and B->A are in sorted form...if not sort them > > > in > > > > O(n log n). > > > > then > > > > first suggestion A1+B1 > > > > second suggestion MIN( A1+B2 , B1+A2) ===> let it be B1+A2 > > > > third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2)====> let it > > > be > > > > A2+B3 > > > > and so on... > > > > > @Dave what will be complexity of above solution...? > > > > i think O(n log n) for sorting and second part (suggestions) O(n).. > > > > > Guys do correct me plz... > > > > > On Thu, Oct 14, 2010 at 11:10 AM, Amod <gam...@gmail.com> wrote: > > > > > @Dave You are partly correct. > > > > > > If i ask for four minimum fares for the round trip then > > > > > first suggestion is what u said : sum the sum of the minimum cost from > > > > > A to B and the minimum cost from B to A > > > > > after that we have to see which combination from both costs, sums up > > > > > least > > > > > > On Oct 14, 9:55 am, Dave <dave_and_da...@juno.com> wrote: > > > > > > @Amod. Isn't the minimum sum the sum of the minimum cost from A to B > > > > > > and the minimum cost from B to A? What am I missing? > > > > > > > Dave > > > > > > > On Oct 13, 11:06 pm, Amod <gam...@gmail.com> wrote: > > > > > > > > Hi > > > > > > > > I think I forgot to mention that the SUM of the ROUND trip i.e. > > > A->B->A > > > > > (sum = going + returning) should be least. > > > > > > > > Please don't take into account any other thing like time and > > > > > > > availability. > > > > > > > So solution is not that straightforward. > > > > > > > > Its like we have two arrays and we have to return least k sum from > > > the > > > > > > > given arrays where we take one element from the first and one from > > > > > > > second in the sum. > > > > > > > > Cheers > > > > > > > Amod > > > > > > > > On Oct 13, 2:26 pm, Shiyam code_for_life <mailshyamh...@gmail.com> > > > > > > > wrote: > > > > > > > > > When a user wants to choose to fly from A to B, suggest the > > > flight > > > > > > > > with lowest fare that's available, here its A1, if A1 is busy > > > then A2 > > > > > > > > and so on > > > > > > > > Repeat the same for B to A. > > > > > > > > > Am I missing something here? > > > > > > > > > Complexity is O( (number of flights from A to B) + number of > > > flights > > > > > > > > from B to A) ) > > > > > > > > > Cheers > > > > > > > > > 'Coding is an art'- Hide quoted text - > > > > > > > > - Show quoted text - > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > > <algogeeks%2bunsubscr...@googlegroups.com> > > > > > . > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > > *Divesh* > > > > (¨`·.·´¨) Always > > > > `·.¸(¨`·.·´¨ ) Keep > > > > (¨`·.·´¨)¸.·´Smiling! > > > > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life > > > 1000's > > > > of reasons 2Smile"- Hide quoted text - > > > > > - Show quoted text - > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > *Divesh* > > (¨`·.·´¨) Always > > `·.¸(¨`·.·´¨ ) Keep > > (¨`·.·´¨)¸.·´Smiling! > > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's > > of reasons 2Smile"- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
