### Akin's blog

By Akin, 4 years ago, ,

I see it sometimes in editorial of CF round and in problems tag ?

But don't know what it is ? I searched and found something like that

Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.

But how to implement it and when it can be implemented for better result ?

Thanks in Advanced :)

•
• +3
•

 » 4 years ago, # |   +6 Two pointers means that in order to solve the problem, there is an invariant involving two indices. So for your problem above.x = a[i]+b[j]. Since both arrays are sorted, we can use to pointers by using the first pointer to "watch" the first array a, and using the second pointer to navigate b.observe that if b[j] < x-a[i] it means we should move forward on the second array.if b[j] > x-a[i] then for all g > j we can't get the answer so i+=1;Notice how both indices are moving in accord, they depend on each other.Hope this helps.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It is generally a useful technique for resolving a variety of problems. I like your explanation arthurugochukwu . Thanks.
•  » » 4 days ago, # ^ |   0 So your solution is wrong? The following comments prove it.
 » 4 years ago, # |   +7 the code, that solves this problem, looks like this: //n - the length of the array A, m - the length of the array B int j=m-1; for (int i=0; i0) && (A[i]+B[j]>x)) { j--; } if (A[i]+B[j]==x) { cout<i1. The following assumption is correct: if (A[i1]+B[j1] == x) and (A[i2]+B[j2] == x) then j2<=j1.So in our code for each i we find the first index j, such as A[i]+B[j]<=x. If (A[i]+B[j]==x), then we find our pair. Otherwise, we continue looking. The total complexity is O(n+m), because i always increases and j always decreases
 » 4 years ago, # |   0 I prefer using only one loop. I think its more beautiful. for(int i = 0, j = m - 1; i < n && j >= 0;) { if(a[i] + b[j] > x) { j--; } else if(a[i] + b[j] < x) { i++; } else { printf("%d + %d = %d\n", a[i], b[j], x); i++; j--; } } The idea is as same as the other people's.
 » 2 years ago, # |   +8 Two years later, I am looking for some stuffs on two pointer to send to a friends and I see my name on a comment :)
•  » » 2 years ago, # ^ |   +27 Two years and you're still pupil. Nice progress :)
•  » » » 2 years ago, # ^ |   +6
•  » » » 2 years ago, # ^ |   -11 I don't code on codeforces dumb-ass. I use codechef, you can go check my profile