algogeeks@googlegroups.com
*Sent:* Mon, 3 May, 2010 12:26:24 PM
*Subject:* Re: [algogeeks] Re: a google question
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted
varun.nagp...@gmail.com
To: Algorithm Geeks algogeeks@googlegroups.com
Sent: Mon, 3 May, 2010 12:26:24 PM
Subject: Re: [algogeeks] Re: a google question
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal
@Gene
I think there is some mistake in this programe.
when the input is :
a[ ] = {30,25,19,16}
b[ ] = {20,18,14,10}
the right result should be 30+20, 30+18, 25+20,30+14
but the output of your programe is 30+20,30+18,25+20,25+18
Best Regards!
2010/5/4 Gene gene.ress...@gmail.com
I propose
@Amit Agarwal
you are missing some pairs having larger some than you mentioned..
for example
7 + 49 = 56 which is greater than 53
similarly
7 + 48
7 + 47
(3 + 49 =52) (50 +1 = 51)
---
Regards
Jitendra Kushwaha
Undergradute Student
Computer Science Eng.
MNNIT, Allahabad
--
You received this
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
@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
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of
The Question only ask to print first n number and each array array is of
size n
So in the worst case we will take combination of 1st element of first array
with all the element of second array.
my above code runs in O(n) taking this considerations... any comments or
test case where it
@satish
ur solution is of o(nlogn) complexty
@ jitendra
suppose p11 and p21 r pointing at index 0 and p12 at 4 and p22 at 1. now
suppose at ths point d s greater than b and c. now u increment p11 and p21.
but it can be a case that a[0] + b[2] is next greatest value bt t wont
work for ur algo.
@divya
I try to simulate what you said for the given array
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1:8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
^ ^
p11 p12
*p11 = 8 and *p12 = 3
index : 0, 1, 2, 3, 4, 5, 6, 7,
slight change in value of c
c = 34 + 2 = 36 //arr1[4] + arr2[0] greatest !!!
my mistake..
--
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,
@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
On May 3, 9:43 am, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@divya
I try to simulate what you said for the given array
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1 : 8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
^ ^
p11 p12
This problem can be simplified to a variation of merge part of merge
sort algorithm.
- Break the set S having n^2 values into n individual arrays of length
n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
- One can observe that each Si has entries which are themselves sorted
within Si.
-
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
16 matches
Mail list logo