0156MediumMathStringSimulation

Punched Reel Product

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stock-take terminal reads tallies off punched paper reels. A reel is written as a run of digit characters, heaviest digit first, and a reel can hold far more digits than any number type on the terminal can carry.

You are handed the reels left_reel and right_reel. Punch and return the reel that records their product. The digits are all you get to work with: feeding either reel into a built-in numeric type, or handing the job to a big-number library, is not allowed.

A reel never starts with a padding zero, the one exception being the single-digit reel "0", which stands for an empty tally. Your answer must obey the same rule.

Examples

Example 1

Input: left_reel = "47", right_reel = "206"
Output: "9682"

Column by column, 47 punched 206 times over lands on 9682, and no padding zero is needed in front.

Example 2

Input: left_reel = "70", right_reel = "30"
Output: "2100"

70 punched 30 times over lands on 2100. The trailing zero of each reel carries through to the answer, and no padding zero is written in front of it.

Example 3

Input: left_reel = "0", right_reel = "5814"
Output: "0"

An empty tally on one reel empties the product, and the answer is punched as the single digit 0 rather than a run of zeros.

Constraints

1 <= left_reel.length, right_reel.length <= 200
left_reel and right_reel hold digit characters only
Neither reel starts with a zero unless the reel is exactly "0"

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def reel_product(left_reel: str, right_reel: str) -> str:

Java

public String reelProduct(String leftReel, String rightReel)

The intended approach

Time O(n * m) where n and m are the reel lengthsSpace O(n + m) for the column buffer

Lay out a column buffer of `n + m` slots, because the product of an n-digit and an m-digit reel never needs more. Multiplying digit i of one reel by digit j of the other lands in column `i + j + 1`, with its overflow going to column `i + j`. Walk both reels from the light end, drop each single-digit product into its column, keep the remainder mod 10 there and push the tens forward; every column is normalised again before it is read, so one pass suffices. Finally shed the one padding zero the buffer may carry.

Pythonentry point: reel_product

def reel_product(left_reel, right_reel):
    # every digit pair once: O(n * m) time, O(n + m) space for the columns
    if left_reel == "0" or right_reel == "0":
        return "0"
    n = len(left_reel)
    m = len(right_reel)
    columns = [0] * (n + m)
    for i in range(n - 1, -1, -1):
        a = ord(left_reel[i]) - 48
        for j in range(m - 1, -1, -1):
            b = ord(right_reel[j]) - 48
            # digit i times digit j lands here, overflow goes one column left
            low = i + j + 1
            cur = columns[low] + a * b
            columns[low] = cur % 10
            columns[low - 1] += cur // 10
    out = "".join(chr(48 + d) for d in columns)
    trimmed = out.lstrip("0")
    if trimmed == "":
        return "0"
    return trimmed

The obvious version

Never multiplies at all: adds the left reel to a running reel once for every unit recorded on the right reel, counting down the right reel by one each time. Addition and the countdown are both plain digit work on strings. Obviously correct, and hopelessly slow for real reel lengths.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_reel_product(left_reel, right_reel):
    def add(x, y):
        i = len(x) - 1
        j = len(y) - 1
        carry = 0
        out = []
        while i >= 0 or j >= 0 or carry:
            s = carry
            if i >= 0:
                s += ord(x[i]) - 48
                i -= 1
            if j >= 0:
                s += ord(y[j]) - 48
                j -= 1
            out.append(chr(48 + s % 10))
            carry = s // 10
        out.reverse()
        return "".join(out)

    def is_empty(s):
        return s.lstrip("0") == ""

    def take_one(s):
        d = list(s)
        k = len(d) - 1
        while k >= 0:
            if d[k] != "0":
                d[k] = chr(ord(d[k]) - 1)
                break
            d[k] = "9"
            k -= 1
        left = "".join(d).lstrip("0")
        if left == "":
            return "0"
        return left

    total = "0"
    counter = right_reel
    while not is_empty(counter):
        total = add(total, left_reel)
        counter = take_one(counter)
    stripped = total.lstrip("0")
    if stripped == "":
        return "0"
    return stripped

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in