Tuesday, June 7, 2011

Equal values of 0s and 1s

You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal. In linear time! tricky but funny

1 comment:

  1. let f(x) = 2* sum(x) - x
    where sum(x) = sum from 0 to x of the input values.

    If f(x) == f(y) then the interval [x+1, y] has equal numbers of 0's and 1's.

    So all you have to do is record the histograms of f() and investigates bins with more than 2 values.

    f(x) is in range [-x,x], so histogram array is of size 2*size + 1 at max

    int histo[2*size + 1] = { 0 };
    int val = 0;
    for (int i = 0; i < size; ++i) {
    val += 2 * array[i] - 1; // incremental eval of 2*sum(x) - x
    histo[val]++;
    if (histo[val] >= 2) { /* we have intervals to print */ }
    }

    ReplyDelete