Re: [algogeeks] Re: subarray wid sum=k
bt how to modify it for getting sum value= k? -- 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] Re: subarray wid sum=k
the problem can be solved in O(n) time without using extra space .using the algorithm of finding the subarray of maximum sum in a given array.(time complexity is O(n) and no extra space). here you just have to stop when you find sum equal to k. -- 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] Re: subarray wid sum=k
here is the solution of O(n) ... int maxSubArray(int array[],int n) // n is the length of the given array ... { int left=0,right=0; // these are to indicate the subscript range on which we got the max array .. int temp_left=0; int max=0,sum=0; for(int i=0;in;i++) { sum += array[i]; if(maxsum) { max=sum; right=i; left=temp_left; } if(sum0) // if the sum is negative .. { sum=0; temp_left=i+1; } } return max; } This'll work On Sun, Sep 4, 2011 at 4:54 AM, tarun kumar taruniit1...@gmail.com wrote: the problem can be solved in O(n) time without using extra space .using the algorithm of finding the subarray of maximum sum in a given array.(time complexity is O(n) and no extra space). here you just have to stop when you find sum equal to k. -- 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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] Re: subarray wid sum=k
In my previous post .. if all the array elements are negative .. then it returns zero and this is also satisfiable .. On Sun, Sep 4, 2011 at 7:02 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: here is the solution of O(n) ... int maxSubArray(int array[],int n) // n is the length of the given array ... { int left=0,right=0; // these are to indicate the subscript range on which we got the max array .. int temp_left=0; int max=0,sum=0; for(int i=0;in;i++) { sum += array[i]; if(maxsum) { max=sum; right=i; left=temp_left; } if(sum0) // if the sum is negative .. { sum=0; temp_left=i+1; } } return max; } This'll work On Sun, Sep 4, 2011 at 4:54 AM, tarun kumar taruniit1...@gmail.comwrote: the problem can be solved in O(n) time without using extra space .using the algorithm of finding the subarray of maximum sum in a given array.(time complexity is O(n) and no extra space). here you just have to stop when you find sum equal to k. -- 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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] Re: subarray wid sum=k
r u sure space used is 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 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] Re: subarray wid sum=k
The problem in this solution might be the fact that you will get the sub array only if the prefix sum is k... so here we are not using prev index. On Fri, Sep 2, 2011 at 3:17 PM, WgpShashank shashank7andr...@gmail.comwrote: I Think We can Use HashTable , as Its Sub-Array you are asking about , its obviously contiguous :D Calculate prefix sum , store it in hashtable as key current index as value , once prefix sum=k, print subarray , also keep track of prev index , so that we can print array from prev_i9ndex to current _index where sum=k Time Complexity O(N) Space Complexity O(N) Correct me if anything wrong ? Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xCl1rX3yv5IJ. 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] Re: subarray wid sum=k
@shasank; i don't think it works... prefix sum means u are taking sum from starting index ... sub array can be from middle ..It is like max sub array in an array problem ...O(n^2) algo is available in Cormen text book .google it . On Fri, Sep 2, 2011 at 6:05 AM, manish kapur manishkapur.n...@gmail.comwrote: r u sure space used is 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 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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] Re: subarray wid sum=k
@Shashank : I think the sub array need not start from the the index 0. For eg: If the array is of size 10, then the sub array can be from index 3 to 7. Here is my solution : Given : int arr[size] , int sum 1. Take an array prefix_sum[size] 2. int temp=0;prefix_sum[0]=0; for(int i=0;isize;i++) { temp+=arr[i]; prefix_sum[i]=temp; } 3. for (int i=0;isize;i++) for(int j=0;j=i;j++) { if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum) printf(%d %d,i,j); // sub array from index i to j is the required sub array } Time : O(n^2) Space : 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 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] Re: subarray wid sum=k
we can do this without taking O(n) space .. but time is O(n^2) as in i already mentioned where the solution is ... On Fri, Sep 2, 2011 at 7:35 AM, Neha Singh neha.ndelhi.1...@gmail.comwrote: @Shashank : I think the sub array need not start from the the index 0. For eg: If the array is of size 10, then the sub array can be from index 3 to 7. Here is my solution : Given : int arr[size] , int sum 1. Take an array prefix_sum[size] 2. int temp=0;prefix_sum[0]=0; for(int i=0;isize;i++) { temp+=arr[i]; prefix_sum[i]=temp; } 3. for (int i=0;isize;i++) for(int j=0;j=i;j++) { if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum) printf(%d %d,i,j); // sub array from index i to j is the required sub array } Time : O(n^2) Space : 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 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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] Re: subarray wid sum=k
we have to consider 3 cases .. 1) that sub array can be in first half 2) that sub array can be in second half 3) that sub array can be in middle . On Fri, Sep 2, 2011 at 7:56 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: we can do this without taking O(n) space .. but time is O(n^2) as in i already mentioned where the solution is ... On Fri, Sep 2, 2011 at 7:35 AM, Neha Singh neha.ndelhi.1...@gmail.comwrote: @Shashank : I think the sub array need not start from the the index 0. For eg: If the array is of size 10, then the sub array can be from index 3 to 7. Here is my solution : Given : int arr[size] , int sum 1. Take an array prefix_sum[size] 2. int temp=0;prefix_sum[0]=0; for(int i=0;isize;i++) { temp+=arr[i]; prefix_sum[i]=temp; } 3. for (int i=0;isize;i++) for(int j=0;j=i;j++) { if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum) printf(%d %d,i,j); // sub array from index i to j is the required sub array } Time : O(n^2) Space : 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 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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] Re: subarray wid sum=k
@bharatkumar..cn u pls share the algo -- 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] Re: subarray wid sum=k
Logic: since n numbers are there,so there can be (2^n)-1 cases.Just as for n bits we have 2^n possible combinations. Keeping above logic in mind,We can also create a binary tree with root node as 0.From there create 2 child nodes:1)number 2) 0. 1st child node indicates that number was taken in subset and 2nd child node indicates that number was not taken.similarly make a tree with all such possible combinations. FInd sum corresponding to all the the paths. If that sum =k(given) then it means subset exists.Else not. Ashima M.Sc.(Tech)Information Systems 4th year BITS Pilani Rajasthan On Fri, Sep 2, 2011 at 5:26 AM, manish kapur manishkapur.n...@gmail.comwrote: @bharatkumar..cn u pls share the algo -- 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] Re: subarray wid sum=k
@ashima..wat will b the complexity of ur algo? -- 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] Re: subarray wid sum=k
@bharat , I never Said that subarray can't start from middle or have to start from 0th index :) Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jUN6eiegbUoJ. 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] Re: subarray wid sum=k
Yes Neha, I Never Said That SubArray has to be Started from 0th index,else What Will be the advantage of this saying subarray anyways, here O(N) time O(N) space solution int prefix_sum = 0; hash_mapint,int find_subarray; int start_index = -1, end_index = -1; for (int i = 0,;i n; ++i) { if (a[i]==k) { start_index = i; end_index = i; break; } prefix_sum += a[i]; if (prefix_sum==k) { start_index = 0; end_index = i; break; } if (find_subarray.find(prefix_sum) == k) { find_subarray[prefix_sum] = i; } else { start_index = find_subarray[prefix_sum] + 1; end_index = i; break; } } if (start_index != -1) { cout Zero sum subarray found. Start index : start_index . End Index: end_index \n; } -2 1 -2 5 -1 4 -6 -7 k=9 subarray will be -2 5-1 4 -6 @all Whats Say ? Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SNpbdnf1PTMJ. 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] Re: subarray wid sum=k
ya , it can start from middle ...but continuous right .. On Fri, Sep 2, 2011 at 4:34 PM, WgpShashank shashank7andr...@gmail.comwrote: Yes Neha, I Never Said That SubArray has to be Started from 0th index,else What Will be the advantage of this saying subarray anyways, here O(N) time O(N) space solution int prefix_sum = 0; hash_mapint,int find_subarray; int start_index = -1, end_index = -1; for (int i = 0,;i n; ++i) { if (a[i]==k) { start_index = i; end_index = i; break; } prefix_sum += a[i]; if (prefix_sum==k) { start_index = 0; end_index = i; break; } if (find_subarray.find(prefix_sum) == k) { find_subarray[prefix_sum] = i; } else { start_index = find_subarray[prefix_sum] + 1; end_index = i; break; } } if (start_index != -1) { cout Zero sum subarray found. Start index : start_index . End Index: end_index \n; } -2 1 -2 5 -1 4 -6 -7 k=9 subarray will be -2 5-1 4 -6 @all Whats Say ? Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SNpbdnf1PTMJ. 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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.