1. Suppose you have Array A and B like this.
2. A = [10,7,3,1] , B = [50,49,48,47,46]
3. Arrange/Assume numbers in a three column table such that First n
rows are the made up of A[1] and members of B. Rest m rows are made up of
B[1] and members of A. Column 3 keeps sum of column 1 and 2. It would look
something like this.
⁃ 10 50 60
⁃ 10 49 59
⁃ 10 48 58
⁃ 10 47 57
⁃ 10 46 56
⁃ 50 10 60
⁃ 50 7 57
⁃ 50 3 53
⁃ 50 1 51
4. Now sort the rows based on column 3 in O(n) time. Remember its a
merge operation of two sorted lists so O(n+m) time.
5. Pick any number of pairs from top. They are in decreasing order of their
value.
This algorithm takes time in O(n). But there might be space complexity
issues if array size is too large.
-Regards
Amit Agarwal
On Mon, May 3, 2010 at 9:48 PM, Jitendra Kushwaha
<jitendra.th...@gmail.com>wrote:
> @Varun
> output for your test cases are as below:
>
> arr1[0] + arr2[0] = 38
> arr1[0] + arr2[1] = 33
> arr1[1] + arr2[0] = 28
>
> arr1[0] + arr2[0] = 38
> arr1[0] + arr2[1] = 37
> arr1[0] + arr2[2] = 36
>
> what i was talking about worst case was that is if one have to find more
> than N elements of array c then it is possible that one of the pointer go
> out of boundry of 1 to N in worst case.
>
>
> On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal <varun.nagp...@gmail.com>wrote:
>
>> @Jitendra
>> I dont think so.Try these 2 examples to check:
>>
>> A[1..n] :20 10 0
>> B[1..n] :18 13 5
>> Ans :38 33 28
>>
>> A[1..n] :20 10 0
>> B[1..n] :18 17 16
>> Ans :38 37 36
>>
>> My conjecture is: In the worst case, instead of combination of 1st
>> element of first array with all elements of second array, we need to
>> instead choose 2 elements from first array and than take combination
>> with all elements of second array. Also before doing this we need to
>> choose from which array should these 2 elements be extracted. I have
>> already suggested before how to do this.
>>
> --
> 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.
>
--
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.
