@Piyush: Try your code with
n = 10
a[10] = {11,22,33,44,55,66,77,88,99,110}
b[10] = {10,20,30,40,50,60,70,80,90,100}
Your code gets
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(88, 100) = 188
(110, 70) = 180
(77, 100) = 177
(110, 60) = 170
(66, 100) = 166
(110, 50) = 160
but it should get
(110, 100) = 210
(110, 90) = 200
(99, 100) = 199
(110, 80) = 190
(99, 90) = 189
(88, 100) = 188
(110, 70) = 180
(99, 80) = 179
(88, 90) = 178
(77, 100) = 177
It fails because, after choosing the first four pairs, it does not
consider all three candidates, (110, 70) = 180, (99, 90) = 189, and
(88, 100) = 188. It only looks at the first and last of these. Later
on, it fails to consider (99, 80) = 179 and (88, 90) = 178.
After you have chosen the maximum pair, every unused pair that is the
last unused pair in both its row and column of the (implicit) n by n
matrix of pairwise sums is a candidate. When you have chosen n-1
pairs, there can be O(sqrt(n)) candidates for the last choice. You are
considering only two of them.
Dave
On Sep 2, 3:09 pm, Piyush Grover <piyush4u.iit...@gmail.com> wrote:
> if I have understood the question correctly then:
>
> a[n-1] + b[i] > a[j] + b[i] for all 0 <= j < n-1
> and a[j] + b[n-1] > a[j] + b[i] for all 0 <= i < n-1
> therefore,
>
> i = j =n-1;
> count = 1;
> S[0] <-- (a[n-1], b[n-1])
> p = a[n-1] + b[n-2];
> q = a[n-2] + b[n-1]
>
> while(count < n){
>
> if(p > q){
> j--;
> S[count++] <-- (a[n-1], b[j]);
> }else{
> i--;
> S[count++] <-- (a[i], b[n-1]);
> }
>
> p = a[n-1] + b[j-1];
> q = a[i-1] + b[n-1];
>
> }
>
> Time complexity: O(n) : http://ideone.com/FXfVj
>
> On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank
> <shashank7andr...@gmail.com>wrote:
>
>
>
> > @Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case
> > it Will be O(N^2) , as we need to find out n such maximum pair , will think
> > about O(N0) Algo, if able to do it, will post the Algo here
>
> > Thanks
> > Shashank Mani
> > Computer Science
> > Birla Institute of Technology,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/-/a14Pj22tbJgJ.
>
> > 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.- 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 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.
