Re: [algogeeks] Re: finding subarray
maintaining cumulative sums of left side of array from index i in in hash, and maintaining variable for right cumulative sums at each j ( j=i+1 till n-1) and check at each value on hash will solve in O(n^2), let me know if im wrong.. surender On Wed, Jan 11, 2012 at 9:12 PM, sravanreddy001 sravanreddy...@gmail.comwrote: @Lucifer: a very good counter example involving the -ve numbers..[:)] I never thought of negative numbers while looking for solution. And I don't see a O(N) solution for this -- 1) Find the first pair (i,j) such that: sum( A[0] .. till A[i]) = sum(B[0] ... B[i]) -- ESP when there are -ve numbers, If No negative numbers its same as one provided before. And, sorting the sums comparing them like you suggested leads us to O(n^2 log n) -- 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/-/4DoZ5nKZd5wJ. 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: finding subarray
sry for last post:
the code bye sravan reddy would not work for negative nos.
but slight modification in if conditions make it work for negative nos too.
by the way nice algo suggested
#includestdio.h
int main(int argc, char **argv){
int a[] = {-2,-3,-4,-19,10};
//int a[]={2,8,-6};
//int a[]={2,2,13,4,7,3,8,12,9,1,5};
int len = sizeof(a)/sizeof(a[0]);
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Possible for \tLeft : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(((left right p2 len-1
a[p2+1]0))|| ((a[p2+1]0))){
p2++;
right = right+ a[p2];
}
else if(((left right p1 0) a[p1-1]0)||
((a[p1-1]0))){
p1--;
left = left + a[p1];
}
else{
printf(Not Possible for \t Left : %d, Right: %d, Center:
%d \n,p1,p2,i);
break;
//return 0;
}
}
}
On Tue, Jan 10, 2012 at 10:42 AM, priyanka jaggi
priyankajag...@gmail.comwrote:
@ankur : in this question, the elements of the array are continuous
i think the solution of shravan reddy is correct and works for negative
nos too.
--
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: finding subarray
I think this wont work for cases with negetive nos
Ex
-2,8,-6
On Tue, Jan 10, 2012 at 6:51 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
solution at this link:
http://ideone.com/ifVIv
for every position, (iteration)
maitain left, right for the sums,
keep adding elements towards the begenning to left, and towards the end to
right, (based on the conditions in the code)
Complexity: outer forloop : O(n)
inner while loop O(n)
total O(n^2) and O(1) space.
its currently printing all the position, center is included to the left
side,
Left : 3, Right: 9, Center: 6
this reads as.. sum(elements at 3,4,5,6) == sum(elements at 7,8,9)
let me know if it needs more explanantion.
for(int i=0;ilen;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1=0 p2 len){
if( left == right){
printf(Left : %d, Right: %d, Center: %d
\n,p1,p2,i);
break;
//return 0;
}
else if(left right p2 len-1){
p2++;
right = right+ a[p2];
}
else if(left right p1 0){
p1--;
left = left + a[p1];
}
else{
//printf(Left : %d, Right: %d, Center: %d
\n,p1,p2,i);
//printf(Not Possible\n);
break;
//return 0;
}
}
}
--
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/-/GoJEA73v8dcJ.
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: finding subarray
The question mentions of Subarray (which is like a substring in the string) I think you are assuming it to be any subset, in that case even O(n^3) time will not be sufficient and its an exponential time algorithm. with the subarray like my assumption, the bruteforce approach will be to find all the n^2 sub array's and for each find if satisfies in O(n) time, using the similar logic, maintain left, right start adding the ends and coming towards the center. which results in O(n^3) time. let me know if my understanding is wrong. -- 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/-/BRDRMATaJo8J. 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: finding subarray
and.. yes for this example, -2, 8, -6 it results in No solution. (or doesn't print anything.) but works if its -2, 8, 6 where (-2+8 == 6) -- 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/-/D9_xTy-LQkAJ. 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: finding subarray
@ankur : in this question, the elements of the array are continuous i think the solution of shravan reddy is correct and works for negative nos too. -- 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.
