Arbitrary_sum

Problem Description (Optional Summary)

The Problem: Write a function that takes such an array A representing integer D and updates it in-place to represent D + 1. Handle potential carries, including the case where the number of digits increases (like 99 + 1 = 100).

Solution Approach

Brute-Force (and why it’s often not allowed/intended):

Convert the array [1, 2, 9] into the integer 129. Add 1: 129 + 1 = 130. Convert 130 back into an array [1, 3, 0]. Limitation: This fails if the integer D is larger than the maximum value the language’s built-in integer type can hold (this isn’t an issue for Python’s runtime integers, but the problem setup often simulates fixed-precision constraints or asks you to avoid this conversion). It also doesn’t modify the array in-place directly.

The Grade-School Algorithm Approach: Think about how you add 1 to a number on paper, like 129 + 1:

Start from the rightmost digit (Least Significant Digit - LSB). Add 1 to the last digit: 9 + 1 = 10. Write down the 0, carry-over the 1. Move to the next digit to the left (2). Add the carry: 2 + 1 = 3. Write down the 3. No carry-over this time (carry is 0). Move to the next digit to the left (1). Add the carry: 1 + 0 = 1. Write down the 1. No carry-over. No more digits, result is 130. Now consider 99 + 1:

Start rightmost: 9 + 1 = 10. Write 0, carry 1. Next digit: 9 + 1 (carry) = 10. Write 0, carry 1. No more digits, but we still have a carry. This means the result needs an extra digit. The result is 100.

Simulating on the Array:

We operate directly on the array A. Increment the last element: A[n-1] += 1. Iterate from right-to-left (from n-1 down to 1). If A[i] == 10 (meaning we had a carry into this position): Set A[i] = 0. Increment the digit to the left: A[i-1] += 1. If A[i] is not 10 after adding the potential carry, then the carry propagation stops, and we can break the loop early. Special Case: After the loop, check if the first digit A[0] became 10. If it did, it means we had a carry out of the most significant digit. Set A[0] = 1. Append a 0 to the end of the array to accommodate the new least significant digit. (The book uses a slightly different but equivalent way: set A[0]=1, A.append(0)).

Complexity Analysis

• Time: O(n)
• Space: O(1)

Notes & Learnings

1. learned how to do reverse loop for i in range(len(A)-1, -1, -1)
2. when checking for carry over also add condition that the pointer has to be greater than 0 for carry ( to avoid appending 0 at the start) if A[i] == 10 and i>0: