# Carry the One > In grade-school subtraction you scribble a mark each time you borrow. Recover those marks. Canonical URL: Domain: Python · Difficulty: medium · Seniority: mid ## Problem We store counters too big for 64 bits as arrays of base-1,000,000,000 limbs, least significant limb first. Subtracting `b` from `a` (with `a` never smaller than `b`) the way you would on paper, some columns force a borrow from the next limb up. Return the limb indices where a borrow is taken, lowest first. ## Worked solution and explanation ### Why this problem exists in real interviews This is grade-school borrow propagation hiding behind a big-integer storage format. When you subtract b from a column by column, each column can be forced to borrow from the column above, and that borrow ripples upward. The interviewer wants to see that you can track the ripple, not that you can call Python's big integers. Here is the trap: the obvious move is to fold both arrays into native ints and subtract, but a - b tells you the difference, not which columns borrowed to produce it. The digits of the answer simply do not encode that. The only way to know where a borrow happened is to redo the subtraction one position at a time, threading a single borrow flag from the least significant limb upward. --- ### Break down the requirements #### Step 1: Line up the columns, treating a shorter b as zeros Because a is never smaller than b, a has at least as many limbs. Walk a's positions and pull b[i] when it exists, treating any missing high-order limb of b as 0. That single guard handles b being shorter without building a padded copy. #### Step 2: Thread one borrow flag, do not judge each column alone At position i the column must cover b[i] plus whatever borrow arrived from below. If a[i] minus the incoming borrow minus b[i] goes negative, this column borrows: record the index and set the outgoing borrow to 1 for the next, more significant column; otherwise clear it to 0. That single flag is what makes the borrow ripple across positions. #### Step 3: Collect the positions in order Because you walk from the least significant limb upward, the indices you record are already lowest first, so you return them as they are. When no column ever borrows, you return an empty list. --- ### The solution **One linear pass with a threaded borrow** ```python def borrow_positions(a, b): positions = [] borrow = 0 for i in range(len(a)): limb_b = b[i] if i < len(b) else 0 if a[i] - borrow - limb_b < 0: positions.append(i) borrow = 1 else: borrow = 0 return positions ``` > **Complexity** > > O(n) time and O(n) space in the worst case, where n is len(a): one left-to-right pass. The native-int alternative that actually answers the question compares the low-order prefixes of a and b, and each comparison rebuilds a growing integer, so it is O(n^2). At the thousands-of-limbs scale real bignum code runs (crypto, exact decimals), that quadratic factor is the whole game. **Independent per-column test** Flag column i whenever a[i] < b[i], deciding each column on its own. It reads clean but is simply wrong: it ignores the borrow flowing in from below, so it misses every column that only borrows because of a ripple. Subtracting 1 from 10^18 flags one column instead of two. **Threaded borrow flag** Carry one borrow forward as you scan, so column i sees the deficit created beneath it. It is O(n), uses only fixed-width limb comparisons, and matches exactly how schoolbook subtraction and production bignum code mark their borrows. > **Interviewers Watch For** > > Whether you thread a single borrow forward instead of judging each column independently, whether you handle b being shorter than a without padding it, and whether you notice that the difference itself cannot tell you where borrows occurred. Strong candidates state the invariant out loud: a is never smaller than b, so the top column never underflows and the borrow always resolves. > **Common Pitfall** > > Two misses dominate. First, testing a[i] < b[i] per column and ignoring the incoming borrow, which silently corrupts any subtraction whose borrow travels more than one position. Second, reaching for int(a) - int(b): it computes the difference fine but throws away the borrow history you were asked to report. --- ## Common follow-up questions - Now return the difference limbs as well, not just the borrow positions. _(Tests the full borrow-subtract: adding the base back into a borrowing column and trimming high-order zero limbs so a true zero renders as [0].)_ - Implement addition in the same limb form and report the carry positions. _(Tests whether the candidate sees carry as the mirror of borrow and grows the array by one limb on overflow.)_ - Drop the a is never smaller than b guarantee. How do you detect and report that b is the larger number? _(Tests comparing magnitudes from the most significant limb down before committing to a subtraction direction.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/carry-the-one-bignum-subtract) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.