0251EasyMathStringBit ManipulationSimulation

Combined Toggle Row

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 test rig has two long rows of toggle switches. A row is recorded as a string of the characters '0' and '1', one character per switch, the most significant switch written first, and the row is read as a count in base two. A recorded row never opens with '0' unless the whole row is the single character '0'.

Given the recorded rows top and bottom, return the row that would show their combined count. Use the same format: base two, most significant switch first, and no opening '0' unless the combined count is zero, in which case the answer is the single character '0'.

A row can hold far more switches than the rig's registers can count, so settle the columns one at a time from the least significant switch, carrying into the next column, rather than reading a whole row into a single number.

Examples

Example 1

Input: top = "1011", bottom = "110"
Output: "10001"

The rows stand for eleven and six, and the seventeen they combine to is written 10001 in base two.

Example 2

Input: top = "10011", bottom = "1101"
Output: "100000"

The rows stand for nineteen and thirteen, and the thirty-two they combine to is written 100000 in base two.

Example 3

Input: top = "0", bottom = "1001"
Output: "1001"

The top row is zero, so the combined count matches the bottom row and is written the same way.

Constraints

1 <= top.length, bottom.length <= 10^4
top and bottom hold only the characters '0' and '1'
Neither row opens with '0' unless it is the single character '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 combine_toggle_rows(top: str, bottom: str) -> str:

Java

public String combineToggleRows(String top, String bottom)

The intended approach

Time O(max(m, n)) where m and n are the row widthsSpace O(max(m, n)) for the returned row

Read both rows from their last character towards their first, keeping one carry bit. Each column adds the carry to whichever rows still have a switch left, writes the low bit of that sum, and hands the rest on as the next carry. The loop keeps going while either row has switches left or a carry is still outstanding, so the final carry becomes an extra leading switch; then the collected columns are turned round to put the most significant switch first.

Pythonentry point: combine_toggle_rows

def combine_toggle_rows(top, bottom):
    i = len(top) - 1
    j = len(bottom) - 1
    carry = 0
    switches = []
    while i >= 0 or j >= 0 or carry:
        column = carry
        if i >= 0:
            if top[i] == "1":
                column += 1
            i -= 1
        if j >= 0:
            if bottom[j] == "1":
                column += 1
            j -= 1
        switches.append("1" if column % 2 else "0")
        carry = column // 2
    switches.reverse()
    return "".join(switches)

The obvious version

Let the language parse each row into an arbitrary-precision integer, add them, then divide the total by two repeatedly to recover the base-two digits. This deliberately takes the shortcut the problem asks a solver to avoid, which is what makes it an independent check.

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_combine_toggle_rows(top, bottom):
    total = int(top, 2) + int(bottom, 2)
    if total == 0:
        return "0"
    digits = []
    while total:
        digits.append(str(total % 2))
        total //= 2
    return "".join(reversed(digits))

How this problem was checked

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