On 03/30/2017 03:14 PM, Chris Dennis wrote:
This is indeed nice… but I presume that we all agree that the best solution
here would be to allow instantiation of an IntSummaryStatistics object in a
specific state.
Of course. I just couldn't resist the challenge of Rémi's nice math
exercise...
Regards, Peter
On Mar 29, 2017, at 2:43 PM, Peter Levart <peter.lev...@gmail.com> wrote:
On 03/29/2017 06:06 PM, Chris Dennis wrote:
Remi: I really have to squint pretty hard to see that as anything other than
“brute-force” - it’s still an O(N) calculation.
Here's O(log2(N)):
static IntSummaryStatistics create(long count, long sum, int min, int max) {
if (count < 2 || min == max) {
return combineProduct(new IntSummaryStatistics(), count, min);
} else {
long minCnt = (count * max - sum) / (max - min);
long maxCnt = count - minCnt - 1;
long minSum = minCnt * min;
long maxSum = maxCnt * max;
long minMaxSum = minSum + maxSum;
int mid = (int) (sum - minMaxSum);
IntSummaryStatistics stats = new IntSummaryStatistics();
combineProduct(stats, minCnt, min);
combineProduct(stats, maxCnt, max);
stats.accept(mid);
return stats;
}
}
static IntSummaryStatistics combineProduct(IntSummaryStatistics stats, long
count, int value) {
IntSummaryStatistics pow2 = null;
while (count > 0) {
if (pow2 == null) {
pow2 = new IntSummaryStatistics();
pow2.accept(value);
} else {
pow2.combine(pow2);
}
if ((count & 1L) == 1L) {
stats.combine(pow2);
}
count >>>= 1;
}
return stats;
}
Regards, Peter
