Last active
August 28, 2021 22:18
-
-
Save keif/8ff8906b90b8f71a8a0b1d87a7c47cbf to your computer and use it in GitHub Desktop.
minSum.js - ah, this is from HackerRank, now it all makes more sense.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// I liked reduce. It's weird, but it's quirky, but I don't find it easy to understand at quick glance for all devs | |
const minSum_short = (num, k) => { | |
return new Array(k) | |
.fill(undefined) // not crazy about this aspect | |
.reduce( | |
(prev) => { | |
// Sort the array high to low | |
const current = prev.sort((a, b) => b - a) | |
// Swap the maximum value with the updated one | |
current[0] = Math.ceil(current[0] / 2) | |
return current | |
}, | |
[...num] | |
) | |
.reduce((prev, current) => prev + current, 0) | |
} | |
// a little more verbose | |
// this is a flavor of the versions I've most often seen online | |
// performs well - may not be the shortest code, but (IMO) easiest to grep | |
const minSum_verbose = (num, k) => { | |
const length = num.length | |
let sortedHighToLow = num.sort((a, b) => b - a) | |
let smallerValues | |
let sum = 0 | |
for (let i = 0; i < k; i += 1) { | |
const maxValue = sortedHighToLow[0] | |
// If maxValue is 1 then there's no point in running more work | |
if (maxValue < 2) { | |
console.warn("stop!") | |
break | |
} | |
// Pre-condition: first item in the array is the largest. This means we should halve its value to minimize the sum. | |
const halvedMax = Math.ceil(maxValue / 2) | |
sortedHighToLow[0] = halvedMax | |
/** | |
* Maintain the pre-condition after mutation. | |
* j starts from the end and works its way back to 2nd element (since array is sorted high to low) | |
*/ | |
for (let j = length - 1; j >= 1; j--) { | |
if (sortedHighToLow[j] > halvedMax) { | |
smallerValues = sortedHighToLow.slice(j + 1) | |
sortedHighToLow = [ | |
...sortedHighToLow.slice(1, j + 1), | |
halvedMax, | |
] | |
sortedHighToLow = sortedHighToLow.concat(smallerValues) | |
break | |
} | |
} | |
} | |
for (let i = 0; i < sortedHighToLow.length; i++) { | |
sum = sum + sortedHighToLow[i] | |
} | |
return sum | |
} | |
// Not as easy to read, not necessarilly the fastest | |
const minSum_fastest = (arr, k) => { | |
let newArr = arr | |
while (k--) { | |
let max | |
let newValue | |
let replacingIndex | |
max = Math.max.apply(Math, newArr) | |
newValue = Math.ceil(max / 2) | |
replacingIndex = newArr.findIndex((value) => value === max) | |
newArr[replacingIndex] = newValue | |
} | |
return newArr.reduce((a, b) => { | |
a + b | |
}) | |
} | |
const tests = [ | |
{ | |
nums: [10, 20, 7], | |
k: 4 | |
} // 14 | |
] | |
console.time(`minSum_short`); | |
tests.forEach(test => { | |
const { nums, k } = test | |
const res = minSum_short(nums, k) | |
console.log(res); | |
}) | |
console.timeEnd(`minSum_short`); | |
console.time(`minSum_verbose`); | |
tests.forEach(test => { | |
const { nums, k } = test | |
const res = minSum_verbose(nums, k) | |
console.log(res); | |
}) | |
console.timeEnd(`minSum_verbose`); | |
console.time(`minSum_fastest`); | |
tests.forEach(test => { | |
const { nums, k } = test | |
const res = minSum_fastest(nums, k) | |
console.log(res); | |
}) | |
console.timeEnd(`minSum_fastest`); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment