LeetCode 3814 - Maximum Capacity Within Budget

LeetCode Problem 3814

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Corrected Solution for Exercise 4.3.1.9

Exercise 4.3.1.9 asks for a generalization of Algorithm A to add two $n$-place numbers in a mixed-radix system with bases $b_0, b_1, \dots, b_{n-1}$ from right to left. Algorithm A in TAOCP §4.3.1 describes standard addition with carry propagation in a single-radix positional system. Here we adapt it to mixed-radix arithmetic, where each digit position has its own base.

Step 1: Representation of mixed-radix numbers

Let the two numbers be

$$X = (x_{n-1}, x_{n-2}, \dots, x_0), \quad Y = (y_{n-1}, y_{n-2}, \dots, y_0),$$

where $0 \le x_i < b_i$ and $0 \le y_i < b_i$. The least significant digit corresponds to $i=0$ with base $b_0$, the next digit to $i=1$ with base $b_1$, and so on.

Let $S = (s_{n-1}, s_{n-2}, \dots, s_0)$ denote the sum and $c_i$ the carry from digit $i$ to $i+1$.

Step 2: Generalized addition algorithm

Algorithm: Mixed-Radix Addition

Input: digits $x_i, y_i$ for $i = 0, \dots, n-1$, bases $b_i$ for $i = 0, \dots, n-1$.

Output: sum digits $s_i$ and final carry $c_n$.

1. Initialize carry: $c_0 \gets 0$.
2. For $i = 0$ to $n-1$:

a. Compute the column sum including carry:

$$t_i \gets x_i + y_i + c_i$$

b. Determine the sum digit modulo the radix of that position:

$$s_i \gets t_i \bmod b_i$$

c. Compute the carry to the next higher position:

$$c_{i+1} \gets \left\lfloor \frac{t_i}{b_i} \right\rfloor$$ 3. Return $S = (s_{n-1}, \dots, s_0)$ and $c_n$.

Step 3: Explanation

• Each digit position uses its own base $b_i$ to determine the sum digit and carry.
• The carry from a less significant digit is added to the next digit sum.
• This algorithm reduces to standard radix-$b$ addition when all $b_i = b$.
• The algorithm performs $n$ iterations, propagating carries independently according to the corresponding digit bases.

Step 4: Example

Consider $n=3$ with bases $(b_0, b_1, b_2) = (2, 3, 4)$. Let

$$X = (2, 1, 0), \quad Y = (1, 2, 3)$$

where $x_0 = 0, x_1 = 1, x_2 = 2$ and $y_0 = 3, y_1 = 2, y_2 = 1$.

Compute step by step:

1. $i=0$: $t_0 = x_0 + y_0 + c_0 = 0 + 3 + 0 = 3$

$s_0 = 3 \bmod 2 = 1$, $c_1 = \lfloor 3 / 2 \rfloor = 1$ 2. $i=1$: $t_1 = x_1 + y_1 + c_1 = 1 + 2 + 1 = 4$

$s_1 = 4 \bmod 3 = 1$, $c_2 = \lfloor 4 / 3 \rfloor = 1$ 3. $i=2$: $t_2 = x_2 + y_2 + c_2 = 2 + 1 + 1 = 4$

$s_2 = 4 \bmod 4 = 0$, $c_3 = \lfloor 4 / 4 \rfloor = 1$

Result: sum digits $S = (s_2, s_1, s_0) = (0, 1, 1)$ with final carry $c_3 = 1$.

The final mixed-radix sum is $(c_3, s_2, s_1, s_0) = (1, 0, 1, 1)$.

Step 5: Summary

The generalization of Algorithm A to a mixed-radix system proceeds digit by digit, using the base of each position to compute the sum digit and carry. The procedure is simple, systematic, and works for any finite sequence of radices $(b_0, \dots, b_{n-1})$.

This completes the required generalization.