Sum in Base Minus Two

Medium

In base -2 the only digits are 0 and 1, and the positions weigh 1, -2, 4, -8, 16, … (powers of -2). This way both positive and negative numbers are written without any sign. For example, [1, 1, 0, 1] = -8 + 4 + 0 + 1 = -3. You are given two numbers first and second in this notation, as digit arrays from the most significant position to the least. Return their sum in the same notation. There are no leading zeros in the input or in the answer: an array is either [0] or starts with 1.

Example 1

first=[1, 1, 0], second=[1] → [1, 1, 1]

[1, 1, 0] is 4 - 2 + 0 = 2 and [1] is 1. Their sum 3 is written in base -2 as 4 - 2 + 1, that is [1, 1, 1].

Example 2

first=[1, 1], second=[1] → [0]

[1, 1] is -2 + 1 = -1, and adding 1 gives 0, which is written as the single digit [0].

Example 3

first=[1], second=[1] → [1, 1, 0]

1 + 1 = 2 = 4 - 2, so [1, 1, 0]: adding two ones already makes the result two digits longer.

Constraints

1 ≤ len(first), len(second) ≤ 1000
Every element is 0 or 1
The numbers have no leading zeros

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math

Similar problems

Turn a Square Clockwise Medium Postfix Calculator Medium Roll an Array to the Right Medium Primes Below a Bound Medium Nth Number Built From Given Primes Medium

Input

first=[1, 1, 0], second=[1]

Expected

[1, 1, 1]

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.