Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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

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 */ } }

let f(x) = 2* sum(x) - x

ReplyDeletewhere 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 */ }

}