Carry the One

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Snap

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.

In grade-school subtraction you scribble a mark each time you borrow. Recover those marks.

Example 1

Input:

a = [0,1], b = [1]

Output:

[0]

Example 2

Input:

a = [0,0,1], b = [1]

Output:

[0,1]

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
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
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.

Common follow-up questions