@aakash: you are given an array A of k values which contain int values in
sorted (asec) order. Now u can understand it as if you have to create a new
array which contains all elements , and sum of every two elements taken at a
time and sum of all three elements taken at a time.
eg if array is {a,b,c,d,e}
then find top max k element from the following
{a,b,c,d,e,a+b,a+c,a+d,a+e,b+c,b+d,b+e,c+d,c+e,d+e, a+b+c, a+b+d, ...,
c+d+e}
this new set contains C(k,1) + C(k,2) + C(k,3) elements.
On Sat, Apr 9, 2011 at 12:13 PM, ArPiT BhAtNaGaR <
[email protected]> wrote:
> WELL my answer is complexity is between n^2 to n
>
> SOLUTION LIES WITHIN THE SOLUTION Array AS:
>
> A= {3 4 5 15 19 20 25}
>
>
> first we have in B={ 3,4} now we have PTR1 @ 5 and PTR2 always
> one less thab PTR1 means @ 4
>
> now from B[0] upto the same element ie 4 add ptr2 and check
> 3+4>5 so we hav
>
> B={3,4,5} now ptr1 @15 and ptr2 @ 5 checking with B[0]
> 3+5<15 & 4+5 <15
> so B={3,4,5,8,9}
> Now we missed one thing that is 12
> so we need one more check that is while we move to to each node we can
> remeber sum that is while on 4 we have 7
>
>
> on 5 we have 12
> so we need to check also we SUM <15 we add 12 so B={3,4,5,8,9,12}
>
> """"""""""""""""""""""IMP NOTE : we check sum only if pointer moving from
> B[0] to reaches the no. itself """"""""""""""""
>
> next we hav ptr1 @ 19 ptr2 @ 15 so 15+b[0] =15+3<19 & 15+4=19
> so we insert B={3,4,5,8,9,12,15,18}
> & sum=3+4+5+8 =12+8=20 as sum>19 so no change
>
> 3,4,5,8,9,12,15,18,19,20, 20+B[0] =23 ,20+b[1]=24 ,25 sooooooooooooo
> onnnnnnnnn
>
>
>
>
> On Fri, Apr 8, 2011 at 11:44 PM, Akash Agrawal
> <[email protected]>wrote:
>
>> what do u mean by* top k values?*
>> can't the answer be 3,4,5,15,3+15 etc
>>
>> Regards,
>> Akash Agrawal
>> http://tech-queries.blogspot.com/
>>
>>
>>
>> On Fri, Apr 8, 2011 at 7:22 PM, saurabh agrawal <[email protected]>wrote:
>>
>>> ou are given an array A of k values which contain int values in sorted
>>> (asec) order. Find top k values (asec) which can either be the number from
>>> the array A, or sum of any two numbers from A or sum of any three numbers
>>> from A. So, if A's values are represented as : a1,a2,...,ak , the possible
>>> numbers can be: a(i), a(i)+a(j), a(i)+a(j)+a(l) for any i,j,l < k
>>>
>>> Ex: A[7] = {3,4,5,15,19,20,25}
>>> output B[7] = {3,4,5,(3+4),(3+5),(4+5),(3+4+5)}
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Arpit Bhatnagar
> (MNIT JAIPUR)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
