ss_96's blog

By ss_96, history, 7 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for i <k

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

print ans