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.
