starter.py contains root_node(output), a legacy function written to confuse: graph-sounding names, a bit-shift "sign trick", math.pow, a list comprehension looking for perfect squares. It takes a list of ints and returns an int.
Your job is to work out what it is meant to compute, then replace it with a clean function:
max_gain(values: list[int]) -> int
Two things are wrong with the legacy version, and the tests check both:
- It has a hidden bug: for some inputs it returns an answer that disagrees with its own obvious intent. The examples below are the correct outputs.
- It is O(n²). Lists can hold
2 * 10**5values in[0, 10**9]; yours must be O(n) time and O(1) extra space.
An empty list returns 0.
max_gain([1, 5, 3, 6, 4]) # 5
max_gain([7, 6, 4, 3, 1]) # 0
max_gain([2, 6, 1, 3]) # 4 (the legacy code says 3 here)
max_gain([]) # 0
Work in stages rather than jumping straight to an answer: rename the variables to what they mean, delete code that can't affect the result, trace a small input by hand, then collapse the loops into a single pass.
Discussion
- What does
(d & 0xFFFFFFFF) >> 31compute for a 32-bitd, and why do obfuscated snippets use tricks like this instead of a comparison? - How would you convince a reviewer that your rewrite is equivalent, apart from the bug you fixed?