A = 0 1 4 5 9 11 20 B = 0 2 3 6 8 13 15 (20, 15) (20, 15) -> (20,15) (20,13) (11,15) -> (20,13) (20,8) (11,15) -> (20,8) (20,6) (11,15) -> assume (20,6) (20,3) (11,15) -> (11,15) (20,3) (9,15) ->
On Mon, Jul 11, 2011 at 1:06 AM, sunny agrawal <sunny816.i...@gmail.com>wrote: > @DK sir > I was just assuming n^2 values as the 2D matrix......not creating > > although i am using a O(n^2) space that keep track of which cell is already > in heap and need not be inserted again........so initially all the need to > be initialized......that will make it O(n^2) > > Now I have a Doubt - Is there any way i can initialize this space so that > overall complexity is O(nlgn) > like making this space static or global (so all memory will be initialized > to zero) or using memset > is that still O(n^2) ?? > > On Mon, Jul 11, 2011 at 12:34 AM, DK <divyekap...@gmail.com> wrote: > >> Largest value is of course A(n) + B(n). >> Second largest value is either A(n) + B(n-1) or A(n-1) + B(n). >> >> Select the largest among both and continue down that array. >> Maintain 2 pairs: >> Pair 1: Hold first value constant, go down the second array. Pair 2: Hold >> 2nd value const. and go down the first array. >> Whenever one element of a pair cannot find a partner, that implies that >> all pairs containing that element have been considered. >> Discard that partner-less element and continue down the array. Take >> special care that duplicate elements are not output. See the output below so >> that things are clearer. (The duplicates case arises when the pair chosen in >> both cases is the same). >> >> eg. >> >> 1 7 9 >> 2 3 4 >> >> >> Pair 1: (9,4) Pair 2: (9,4) -> Output (9,4) = 13 >> Pair 1: (9, 3) Pair 2: (7,4) -> Output (9,3) = 12 >> Pair 1: (9, 2) Pair 2: (7,4) -> Output (7,4) or (9,2) -- assume (9,2) was >> output = 11 >> Pair 1: (7,4) Pair 2: (7,4) -> Ouput (7,4) = 11 >> Pair 1: (7,3) Pair 2: (1, 4) -> Output (7, 3) = 10 >> Pair 1: (7,2) Pair 2: (1,4) -> Output (7,2) = 9 >> Pair 1: (1,4) Pair 2: (1,4) -> Output (1,4) = 5 >> Pair 1: (1,3) Pair 2: (1,3) -> Output (1,3) = 4 >> Pair 1: (1,2) Pair 2: (1,2) -> Output (1,2) = 3 >> Pair 1: (empty) Pair 2: (empty) -> End >> >> O(N) algorithm. Descending order printing of pairs. >> >> @Sunny: Your time complexity is O(N^2) as creating that array will take >> O(N^2) time. >> @Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but >> (9,3) will not. >> >> -- >> DK >> >> http://twitter.com/divyekapoor >> http://www.divye.in >> >> -- >> 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/-/uJEiQKMYJnMJ. >> >> 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. >> > > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
