Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
Given two numbers arr1 and arr2 in base -2, return the result of adding them together.
Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.
Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.
Example 1:
Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1] Output: [1,0,0,0,0] Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.
Example 2:
Input: arr1 = [0], arr2 = [0] Output: [0]
Example 3:
Input: arr1 = [0], arr2 = [1] Output: [1]
Constraints:
1 <= arr1.length, arr2.length <= 1000arr1[i] and arr2[i] are 0 or 1arr1 and arr2 have no leading zerosProblem summary: Given two numbers arr1 and arr2 in base -2, return the result of adding them together. Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1. Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math
[1,1,1,1,1] [1,0,1]
[0] [0]
[0] [1]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1073: Adding Two Negabinary Numbers
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int i = arr1.length - 1, j = arr2.length - 1;
List<Integer> ans = new ArrayList<>();
for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
int a = i < 0 ? 0 : arr1[i];
int b = j < 0 ? 0 : arr2[j];
int x = a + b + c;
c = 0;
if (x >= 2) {
x -= 2;
c -= 1;
} else if (x == -1) {
x = 1;
c += 1;
}
ans.add(x);
}
while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
ans.remove(ans.size() - 1);
}
Collections.reverse(ans);
return ans.stream().mapToInt(x -> x).toArray();
}
}
// Accepted solution for LeetCode #1073: Adding Two Negabinary Numbers
func addNegabinary(arr1 []int, arr2 []int) (ans []int) {
i, j := len(arr1)-1, len(arr2)-1
for c := 0; i >= 0 || j >= 0 || c != 0; i, j = i-1, j-1 {
x := c
if i >= 0 {
x += arr1[i]
}
if j >= 0 {
x += arr2[j]
}
c = 0
if x >= 2 {
x -= 2
c -= 1
} else if x == -1 {
x = 1
c += 1
}
ans = append(ans, x)
}
for len(ans) > 1 && ans[len(ans)-1] == 0 {
ans = ans[:len(ans)-1]
}
for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return ans
}
# Accepted solution for LeetCode #1073: Adding Two Negabinary Numbers
class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
i, j = len(arr1) - 1, len(arr2) - 1
c = 0
ans = []
while i >= 0 or j >= 0 or c:
a = 0 if i < 0 else arr1[i]
b = 0 if j < 0 else arr2[j]
x = a + b + c
c = 0
if x >= 2:
x -= 2
c -= 1
elif x == -1:
x = 1
c += 1
ans.append(x)
i, j = i - 1, j - 1
while len(ans) > 1 and ans[-1] == 0:
ans.pop()
return ans[::-1]
// Accepted solution for LeetCode #1073: Adding Two Negabinary Numbers
struct Solution;
impl Solution {
fn add_negabinary(mut arr1: Vec<i32>, mut arr2: Vec<i32>) -> Vec<i32> {
let n = arr1.len();
let m = arr2.len();
arr1.reverse();
arr2.reverse();
let mut carry = 0;
let mut res = vec![];
let mut i = 0;
while i < n.max(m) || carry != 0 {
if i < n {
carry += arr1[i];
}
if i < m {
carry += arr2[i];
}
res.push(carry & 1);
carry = -(carry >> 1);
i += 1;
}
while let Some(&0) = res.last() {
res.pop();
}
res.reverse();
if res.is_empty() {
vec![0]
} else {
res
}
}
}
#[test]
fn test() {
let arr1 = vec![1, 1, 1, 1, 1];
let arr2 = vec![1, 0, 1];
let res = vec![1, 0, 0, 0, 0];
assert_eq!(Solution::add_negabinary(arr1, arr2), res);
let arr1 = vec![1];
let arr2 = vec![1];
let res = vec![1, 1, 0];
assert_eq!(Solution::add_negabinary(arr1, arr2), res);
let arr1 = vec![1];
let arr2 = vec![1, 1];
let res = vec![0];
assert_eq!(Solution::add_negabinary(arr1, arr2), res);
}
// Accepted solution for LeetCode #1073: Adding Two Negabinary Numbers
function addNegabinary(arr1: number[], arr2: number[]): number[] {
let i = arr1.length - 1,
j = arr2.length - 1;
const ans: number[] = [];
for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
const a = i < 0 ? 0 : arr1[i];
const b = j < 0 ? 0 : arr2[j];
let x = a + b + c;
c = 0;
if (x >= 2) {
x -= 2;
c -= 1;
} else if (x === -1) {
x = 1;
c += 1;
}
ans.push(x);
}
while (ans.length > 1 && ans[ans.length - 1] === 0) {
ans.pop();
}
return ans.reverse();
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.