Re: [algogeeks] all subarray with sum zero
As I understand it, it is the subset sum problem which is known to be NP-Complete. The known algorithms to solve the problems take exponential time to solve the problem. 'Meet in the middle' algorithm is one of the efficient ones. A polynomial time approximate algorithm is available for solving the problem. Refer: http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm On Tue, Sep 18, 2012 at 9:41 AM, pankajsingh wrote: > it wud give u continuous...subarray...if u want non continuous..question > shud be subsequence...and for that u need to all combination O(n^20..which > is offcourse bruteforce... > > -- > 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. > -- Regards Bharat Singhvi M.Tech Final Year, Dept. of Computer Science and Engineering, IIT Bombay. -- 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.
Re: [algogeeks] all subarray with sum zero
Because you sort the array you may have values such that the indices are in the wrong order e.g your 'end' position is less than your 'start' position. You need to check for this, however if you use an inplace sorting algorithm this becomes easier. Additionally you may have up to O(n^2) occurrences so when you say 'now check for consecutive value which have same value' you should do a binary search for the end position instead. If you do as you said you may take O(n) per search. You want to report the ranges to avoid having to have report each occurrence. On 18 September 2012 05:11, pankajsingh wrote: > it wud give u continuous...subarray...if u want non continuous..question > shud be subsequence...and for that u need to all combination O(n^20..which > is offcourse bruteforce... > > -- > 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. > -- 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.
Re: [algogeeks] all subarray with sum zero
make a sum array..such that..sum[i]=sum of number from 0 to i-1make a node which has 2 data..sum[i] and ith index itself..sort this node array according to sum[i]...now check for consecutive value which have same value...corresponding index i,j to that sum nodes will be start and end of subarray...look for all such subarray..its an O(nlgn)..solution...:) hope it works..!! -- 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.
Re: [algogeeks] all subarray with sum zero
it wud give u continuous...subarray...if u want non continuous..question shud be subsequence...and for that u need to all combination O(n^20..which is offcourse bruteforce... -- 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.
Re: [algogeeks] all subarray with sum zero
contiguous or non-contiguous ? On Tue, Sep 18, 2012 at 1:23 AM, rahul sharma wrote: > Plz provide me efficeient sol. 4 thisthnx > > -- > 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. > -- 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.
[algogeeks] all subarray with sum zero
Plz provide me efficeient sol. 4 thisthnx -- 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.
