Expand description
§Lobby
The highest possible joltage is made by choosing the maximum value for the most significant digit (leaving enough batteries over to make the rest of the bank), then the maximum value for the second most significant digit and so on.
One approach is to scan from left to right checking for the maximum. While the complexity is
technically O(n) we do have to scan the same digits multiple times (up to twelve in part two).
Instead, starting with enough batteries to make the bank, we scan from right to left. If we encounter a battery greater than or equal to the leading battery in the bank then we replace it. The replaced battery is then checked against the next battery, “bubbling” up from right to left just like the infamous sorting algorithm.
While the worst case complexity of bubble sort is O(n²), in practice this approach is much
faster due to the randomized nature of the inputs.