The problem statement:

There is an array given of 1s and -1s and there is a distance K,the output required is the maximum no of pairs such that their sum is 0 and both the numbers are within K distance.

eg: for array:

1 -1 1 -1 and K = 1 answer:2

This can be done with brute force,but i think there would a more efficient algorithm than just brute force.Can anyone please suggest something better,a pseudo code or is there any known algorithm for this?

Edit:A number can be taken only once.

Thanks.

In your example, shouldn't the answer be 3? With pair of indexes being: 0,1 & 1,2 & 2,3 .

A number can be taken only once

Well, that simplifies it. You can use two pointers i and j for 1 and -1 respectively. Should be done in O(n) time.

Can you please elaborate a bit about the approach?

Thanks

I haven't worked it out thoroughly, but you can think on this lines. Index i is used for 1 and index j for -1. Initialize both i=0 and j=0. Increment and i and j till a[i]=1 and a[j]=-1. When a[i] is equal to 1 and a[j] is equal to -1, check the distance. If the distance is greater than k, increase the lesser of i and j, until it is less than or equal to k and sum is 0.

Can we use iterative DFS or BFS here.Will it be feasible?

No. I don't think there is a need to do so.

Alright,Thanks.

Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).for i <k

if(a[i]!=a[i+k]) ans++

print ans