@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.
