Java 9 and IntSummaryStatistics et al.

[Peter Levart]

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