### Abinash's blog

By Abinash, 7 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 ?  Comments (9)
 » 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
 » 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.
•  » » » 