## Problem An unsigned integer is represented by a fixed-size array of decimal digits in most-significant-first order. Add one and return the resulting digit array. Do not convert the entire input to an integer, string, linked collection, or dynamically appended list. You may modify the input array. If every digit is `9`, allocate one new fixed-size array of length `n + 1`; otherwise return the updated original array. ### Function Contract Implement `plusOneFixedDigits(digits)`. ### Constraints & Assumptions - `1 <= len(digits) <= 200,000`. - Every element is an integer from `0` through `9`. - The representation has no leading zero unless the number itself is zero. - The restriction against a dynamic list is part of the exercise. ### Clarifying Questions to Ask - Is input mutation allowed? Yes. - Can the output need one extra digit? Yes, only when the input is all nines. - Should `[0]` become `[1]`? Yes. ```hint Propagate from the least significant digit Scan right to left. A digit below nine can absorb the carry and lets you return immediately; a nine becomes zero and keeps the carry alive. ``` ### Examples ```text [1,2,3] -> [1,2,4] [1,2,9] -> [1,3,0] [9,9,9] -> [1,0,0,0] [0] -> [1] ``` ### Evaluation Focus - Handles carry propagation and the all-nines expansion. - Does not use whole-number conversion or dynamic append operations. - Runs in `O(n)` worst-case time and uses `O(1)` extra space unless expansion is required. ### Extensions to Discuss 1. How would you add an arbitrary nonnegative integer instead of one? 2. How would little-endian digit order simplify or complicate the loop? 3. What changes for a singly linked list representation?