can you do it for some example where k > N... i am confused On Wed, Feb 22, 2012 at 12:22 AM, atul anand <[email protected]>wrote:
> if i am getting it right ,,,, > input has only positive number then > if k <= N (number of elements) , then it would similar to finding kth > smallest element in the array. because we can consider each element in the > input as a sub array. > > now if k > N , then we need to find (k-N)th smallest element which should > be sum two or more elements. > > On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal > <[email protected]>wrote: > >> i dont know if a better solution exists >> but here is one with complexity O(N*logS)... >> N = no of elements in array >> S = max sum of a subarray that is sum of all the elements as all are >> positive >> >> algo goes as follows >> do a binary search in range 0-S, for each such candidate sum find how >> many sums are smaller than candidate sum >> >> there is also need to take care of some cases when there are exactly k-1 >> sums less than candidate sum, but there is no contigious where sum = >> candidate sum. >> >> >> On Tue, Feb 21, 2012 at 11:02 PM, shady <[email protected]> wrote: >> >>> Problem link <http://www.spoj.pl/ABACUS12/status/ABA12E/> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Sunny Aggrawal >> B.Tech. V year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> 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. > -- 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.
