[algogeeks] Re: zero sum subarray
The same technique proposed by Raj + sort PrefixSum array and process it. On 6 ноя, 21:41, Raj rajmangaltiw...@gmail.com wrote: Compute PrefixSum Array. PrefixSum[i]=a[0]+a[1]+a[2]++a[i-1]+a[i] Now problem reduces to finding two elements having same value. For PrefixSum[i], search an element having value PrefixSum[i] in array PrefixSum from indices 0 to i-1. Linear search would cost O(n^2), balanced tree O(nlogn), hash O(n). -- 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Maximum subarray whose sum is zero
I believe the space complexity should be O(n) since you need to store the cumulative sum corresponding to each of the elements from the input starting from the first element. On Wed, Dec 1, 2010 at 12:04 AM, Prims topcode...@gmail.com wrote: I got the solution to use a hash table storing partial sums a[0], a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i Whenever a collision happens, then it is the sub array from i to the last summand. This involves O(N) Time complexity but i what is the space complexity in this case? On Nov 30, 10:19 pm, Prims topcode...@gmail.com wrote: There is an unsorted array of positive and negative integers. I need to find out maximum sub array whose sum is zero efficiently. I can able to provide an answer in O(N^2) time complexity with O(N) Space Complexity Can anyone know better than this? -- 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, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Maximum subarray whose sum is zero
Hello Algoose I believe the maximum space needed in the hashtable is O(max positve - (max negative value). Since the possible cumulative sum is of that order. Correct me if i am wrong On Dec 2, 12:00 pm, Algoose chase harishp...@gmail.com wrote: I believe the space complexity should be O(n) since you need to store the cumulative sum corresponding to each of the elements from the input starting from the first element. On Wed, Dec 1, 2010 at 12:04 AM, Prims topcode...@gmail.com wrote: I got the solution to use a hash table storing partial sums a[0], a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i Whenever a collision happens, then it is the sub array from i to the last summand. This involves O(N) Time complexity but i what is the space complexity in this case? On Nov 30, 10:19 pm, Prims topcode...@gmail.com wrote: There is an unsorted array of positive and negative integers. I need to find out maximum sub array whose sum is zero efficiently. I can able to provide an answer in O(N^2) time complexity with O(N) Space Complexity Can anyone know better than this? -- 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, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] N companies merge
Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge? -- 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Maximum subarray whose sum is zero
Hello 2010/12/3 Prims topcode...@gmail.com: I believe the maximum space needed in the hashtable is O(max positve - (max negative value). I use the same algorithm as you do and I think you could use a smaller space by handling collisions. So the space complexity might be O(N) -- 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: zero sum subarray
Hello Punnu, 2010/12/1 Puneet Ginoria punnu.gino...@gmail.com: You may solve it using depth first search. it will give you all possible solutions dfs? more details, plz? -- 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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
