tag:blogger.com,1999:blog-6314876008291942531.post663124948727247934..comments2021-03-28T11:31:00.109-07:00Comments on Antonio Gulli's coding playground: Equal values of 0s and 1sUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-89226477364508196462012-01-13T08:45:55.351-08:002012-01-13T08:45:55.351-08:00let f(x) = 2* sum(x) - x where sum(x) = sum from 0...let f(x) = 2* sum(x) - x<br />where sum(x) = sum from 0 to x of the input values.<br /><br />If f(x) == f(y) then the interval [x+1, y] has equal numbers of 0&#39;s and 1&#39;s.<br /><br />So all you have to do is record the histograms of f() and investigates bins with more than 2 values.<br /><br />f(x) is in range [-x,x], so histogram array is of size 2*size + 1 at max<br /><br />int histo[2*size + 1] = { 0 };<br />int val = 0;<br />for (int i = 0; i &lt; size; ++i) {<br /> val += 2 * array[i] - 1; // incremental eval of 2*sum(x) - x<br /> histo[val]++;<br /> if (histo[val] &gt;= 2) { /* we have intervals to print */ }<br />}Pascalhttps://www.blogger.com/profile/02506306462425421142noreply@blogger.com