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