ss_96's blog

By ss_96, history, 4 weeks 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.

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A number can be taken only once

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please elaborate a bit about the approach?

        Thanks

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Alright,Thanks.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for i <k

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

print ans