Community Credit Carry Ledger
Normalize linked-list digits in a given base while preserving their value
A social network stores a community's credit balance in a singly linked ledger. The first node represents the lowest place value, and each following node represents the next power of base.
Pending adjustments have already been combined into the nodes, so a node's value may be negative or greater than a normal digit. If the node values are a₀, a₁, …, aₙ₋₁, the ledger represents:
a₀ + a₁ × base + a₂ × base² + … + aₙ₋₁ × baseⁿ⁻¹.
The represented balance is guaranteed to be nonnegative. An empty ledger represents zero.
Normalize the ledger and return its head. The result must represent exactly the same balance, with every node value between 0 and base - 1, inclusive. Keep the lowest place value first, and remove unnecessary zeros from the high-value end. Represent zero with exactly one node containing 0.
Perform the normalization by updating the linked list. Reuse existing nodes that remain in the result, and create nodes only when additional high-order digits are needed or when the input is empty. Do not copy the ledger into an array or convert its complete balance into a single integer. Use constant auxiliary space, excluding newly required output nodes.
Examples
Example 1
Input: head = [15,-3,2], base = 10 Output: [5,8,1]
In base 10, the ledger represents 15 − 3 × 10 + 2 × 100. The oversized lowest coefficient produces a carry, while the negative next coefficient requires borrowing from the following place.
Example 2
Input: head = [-7,0,1], base = 10 Output: [3,9]
The lowest coefficient is negative, so normalization must borrow across the zero coefficient before reaching the positive high-order coefficient.
Example 3
Input: head = [0,0], base = 2 Output: [0]
Both coefficients are zero. The normalized ledger must retain only one zero node.
Constraints
- The list contains between 0 and 6000 nodes.
- -1000 <= node.val <= 1000
- 2 <= base <= 36
- The balance represented by the input list is nonnegative.
- The returned list must use constant auxiliary space, excluding newly required output nodes.
The intended solution takes linear time in the input and output lengths and constant auxiliary space. In JavaScript, Math.floor is necessary for negative carries; truncation toward zero is incorrect.
Hints
Show hint 1Hint 1
Process nodes from the lowest place value upward, carrying any unresolved adjustment into the next node.
Show hint 2Hint 2
For a possibly negative coefficient x, use floor division by base so that x minus base times the quotient is always a valid digit. Track the last nonzero normalized node.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you adapt the representation and normalization rules to allow negative total balances?
- If the ledger were stored highest-place-first, how would that change the traversal and space requirements?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem