0705MediumStringBacktracking

Consistent Stock-Taking Tape

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-taking machine prints its readings onto a paper tape as one unbroken run of digits with nothing separating them. tape is that run.

The tape is consistent when its digits can be cut, left to right and with no digit left over, into three or more whole numbers such that every number from the third onwards equals the sum of the two numbers immediately before it.

No number in the cut may carry a leading zero. A single 0 is a legal number, but 07 and 012 are not.

Return true when the tape is consistent, and false otherwise.

Examples

Example 1

Input: tape = "48122032"
Output: true

Cutting the tape as 4, 8, 12, 20, 32 uses every digit, and `4 + 8 = 12`, `8 + 12 = 20` and `12 + 20 = 32`, so the tape is consistent.

Example 2

Input: tape = "9099"
Output: true

Cutting the tape as 9, 0, 9, 9 uses every digit, and `9 + 0 = 9` and `0 + 9 = 9`. The single `0` is a legal number, so the tape is consistent.

Example 3

Input: tape = "5713"
Output: false

The cuts into three or more numbers are 5, 7, 1, 3 / 5, 7, 13 / 5, 71, 3 / 57, 1, 3, and none of them has every number from the third onwards equal to the sum of the two before it, so the tape is not consistent.

Constraints

1 <= tape.length <= 35
tape consists only of digits.

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 is_summing_tape(tape: str) -> bool:

Java

public boolean isSummingTape(String tape)

The intended approach

Time O(n^4) worst case for a tape of n digits: O(n^2) pairs of opening numbers, and checking a pair walks up to O(n) further numbers each up to n digits wide.Space O(n) for the digit strings of the running sums.

Once the first two numbers of the cut are fixed, every later number is determined, so the search only has to enumerate where the first number ends and where the second one ends. For each such pair, walk forward comparing the digits of the required sum against the tape at the current position and advance by that many digits, accepting only when the walk lands exactly on the end of the tape. A number of two or more digits starting with '0' is rejected, and because extending such a number keeps the same leading digit the outer scan can stop as soon as the first number is illegal.

Pythonentry point: is_summing_tape

def is_summing_tape(tape):
    # O(n^2) choices for the opening two numbers; once they are fixed every later
    # number is forced, so each choice is checked by matching the forced digits.
    n = len(tape)

    def legal(piece):
        return len(piece) == 1 or piece[0] != "0"

    for i in range(1, n - 1):
        first = tape[:i]
        if not legal(first):
            break                     # a longer opening number also starts with '0'
        a = int(first)
        for j in range(i + 1, n):
            second = tape[i:j]
            if not legal(second):
                break
            b = int(second)
            x, y = a, b
            pos = j
            ok = True
            while pos < n:
                nxt = str(x + y)
                if not tape.startswith(nxt, pos):
                    ok = False
                    break
                pos += len(nxt)
                x, y = y, x + y
            if ok:
                return True
    return False

The obvious version

Enumerate every way of cutting the tape into numbers, skipping any piece with a leading zero, and test each complete cut against the summing rule afterwards. Exponential in the tape length, but it makes no use of the fact that the opening pair fixes the rest.

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_is_summing_tape(tape):
    n = len(tape)
    found = [False]

    def walk(pos, pieces):
        if found[0]:
            return
        if pos == n:
            if len(pieces) >= 3:
                for k in range(2, len(pieces)):
                    if pieces[k] != pieces[k - 1] + pieces[k - 2]:
                        return
                found[0] = True
            return
        for end in range(pos + 1, n + 1):
            chunk = tape[pos:end]
            if len(chunk) > 1 and chunk[0] == "0":
                continue
            walk(end, pieces + [int(chunk)])

    walk(0, [])
    return found[0]

How this problem was checked

Reference solution executed against 27 test cases — 27 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