@correction..
1) Find the first pair (i,j) such that:
/*
sum( A[0] .. till A[i]) = sum(B[0] ... B[j])
*/
On Jan 10, 6:13 pm, Lucifer <sourabhd2...@gmail.com> wrote:
> @priyanka..
>
> I don't think it will work...
>
> Say for ex- 1,-1,3,5,1,-3 ... the answer should be (3),(5,1,-3)..
> Will the above fix give the correct answer for the given input ??
>
> Also, i see a couple of flaws in the checks...
> Say, Left > right and p2 = len -1, then it will actually take A[len]
> into consideration which is wrong..
> Secondly, if (left > right && p2 < len -1) passes then irrespective of
> whether A[p2+1] is smaller or greater than 0, it will be added to
> 'right'...
>
> ---------------------------------
>
> The left/right logic will seamlessly work for positive nos... For it
> to work for negative nos., the considered inputs need to sorted...
>
> Basically what we are trying to do here is generate cumulative sums on
> the fly starting at index 'i' towards left and right and see if there
> is a matching value... if the generated cumulative values on either
> side are not sorted then its difficult to ensure that we will be able
> to catch a 'matched' value if we incremently work on 'left' and
> 'right' (pointers)..
>
> ---------------------------------------------------------------------------
> --------
> If the left/right logic is correct, then the following problem should
> be solvable in O(n) without extra space...
> Say, given 2 arrays A[n] and B[n] (not sorted and contains both -ive
> and +ive integers)...
> 1) Find the first pair (i,j) such that:
> sum( A[0] .. till A[i]) = sum(B[0] ... B[i])
> /*
> this is exactly what we are trying to solve using left/right
> logic, here left = A[0],right= B[0], p1 = 0, p2 =0, and we will
> continue till p1 < len and p2 < len...
> */
>
> 2) A variation of the first part... find (i,j) such that (i+j) is
> maximum...
>
> Well looking at the above problem, i do see a nlogn solution, but not
> sure if it can be solved in O(n)...
>
> ------------------------------------------
> @All
>
> Can the above problem be solved in O(n),, if yes, then we can do it in
> O(n^2) using the previously presented algo.. otherwise the runtime
> would be O(n^2 log n)...
>
> Posting in a hurry. If i m wrong, plz do correct me...
> ----------------------
>
> ----------------------------
>
> On Jan 10, 1:27 pm, priyanka jaggi <priyankajag...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 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
>
> > #include<stdio.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;i<len;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.com>wrote:
>
> > > @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.
