Tuesday, January 11, 2011

Binary array !!!

Given an array of 0's and 1's. only, find the maximum length of the subarray such that the number of 0's and 1's in that subarray are equal.

9 comments :

  1. change 0 to -1 on the original array. now define S[i] = a[1] + ... + a[i] (a being the input)
    you want to find indices i and j such that a[i]+...+a[j] = 0
    that is the same as
    S[j]-S[i-1] = 0
    S[j] = S[i-1]
    now you can hash these values (they range from -n to n, so you can do this in O(n) memory)and find the indices in O(n).

    ReplyDelete
  2. in order to find the maximum j-i, you can keep a max hash with the index of the max and a min hash. now find the largest difference subtracting.

    ReplyDelete
  3. @imavalon ... there is a small catch
    if(s[0] - a[0] == s[n-1]) len = n;
    this is the case when the max subarray is the whole array ....
    further there is no need of hash map .... u can take an array of size 2n+1 ... and store the first index containing the value seen and compute difference whenever u see the value again ..
    Regards

    ReplyDelete
  4. find the subarray whose sum is the half of the size of the subarray

    ReplyDelete
  5. @vivek ... and how will you do that ... ?? (remember you need to consider all the possible subarrays )
    Regards

    ReplyDelete
  6. A linear sweep through the array would do it.

    1. XOR neighbors, maintain two counters;
    2. if (XOR result is 0 AND a[i] is 0)
    increment zeroCount;
    else if (XOR result is 0 AND a[i] is 1)
    increment oneCount;
    3. return min(zeroCount, oneCount);

    ReplyDelete
  7. Sweep through the input maintaining the zero-one balance information.
    Balance is defined as follows:
    balance = 0 (initialization)
    If we find a '1' in the input increment by 1, else decrement by 1(we found a zero).

    balance = 0;
    max_length = 0;

    for(int i=0; i<input(length); i++) {

    if (input[i] == 1)
    balance = balance + 1;
    else
    balance = balance - 1;

    if(balance ==0) {
    max_length++;
    }

    }

    max_length has the answer.

    ReplyDelete
  8. @dayadru .... ur solution only consider the case in which subarray starts at position 0.

    Regards

    ReplyDelete