Instantly share code, notes, and snippets.

# Muzietto/MinMaxDivision.js Created Dec 31, 2016

Human-readable solution for the MinMaxDivision puzzle at Codility (https://codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/)
 function solution(K, M, A) { // M is a red herring return minimalLargeSumBinarySearch(K, A); } function minimalLargeSumBinarySearch(maxNumBlocks, arra) { var lowerBoundLargeSum = Math.max.apply(null, arra); var upperBoundLargeSum = arra.reduce((a,c)=>a+c,0); var result = -1; while (lowerBoundLargeSum <= upperBoundLargeSum) { var tentativeLargeSum = Math.floor((lowerBoundLargeSum+upperBoundLargeSum)/2); if (tentativeLargeSumIsPossible(arra, maxNumBlocks, tentativeLargeSum)) { result = tentativeLargeSum; // OK, but... // try a smaller one upperBoundLargeSum = tentativeLargeSum - 1; } else { // try a larger one lowerBoundLargeSum = tentativeLargeSum + 1; } } return result; } function tentativeLargeSumIsPossible(arra, maxNumBlocks, tentativeLargeSum) { var curBlockSum = 0; var numBlocks = 1; // at least... for (let elem of arra) { if (curBlockSum + elem <= tentativeLargeSum) { // make curBlock bigger curBlockSum += elem; } else { // start a new block containing element numBlocks++; curBlockSum = elem; } if (numBlocks > maxNumBlocks) return false; } return true; }