Skip to content

Instantly share code, notes, and snippets.

@Muzietto
Created December 31, 2016 08:37
Show Gist options
  • Save Muzietto/ac26b8e3272920ebfb30850aa94536e8 to your computer and use it in GitHub Desktop.
Save Muzietto/ac26b8e3272920ebfb30850aa94536e8 to your computer and use it in GitHub Desktop.
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment