Adding Two Negabinary Numbers - Practice Coding Problems

Adding Two Negabinary Numbers - Problem

Array Math Medium

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 = -8 + 4 + 1 = -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.

Input & Output

Example 1 — Basic Addition

$ Input: arr1 = [1,1,0,1], arr2 = [1,0,1]

› Output: [1,0,0]

💡 Note: arr1 represents (-2)³+(-2)²+(-2)⁰ = -8+4+1 = -3. arr2 represents (-2)²+(-2)⁰ = 4+1 = -1. Sum: -3+(-1) = -4, which in base -2 is [1,0,0] = (-2)² = 4.

Example 2 — Simple Case

$ Input: arr1 = [1], arr2 = [1]

› Output: [1,1,0]

💡 Note: Both arrays represent -1 in base -2. Sum: -1+(-1) = -2, which in base -2 is [1,1,0] = (-2)²+(-2)¹ = 4+(-2) = 2. Wait, let me recalculate: [1] = (-2)⁰ = 1, so 1+1 = 2, which in base -2 is [1,1,0].

Example 3 — Zero Result

$ Input: arr1 = [1], arr2 = [1,1]

› Output: [0]

💡 Note: arr1 = [1] represents 1. arr2 = [1,1] represents (-2)¹+(-2)⁰ = -2+1 = -1. Sum: 1+(-1) = 0.

Constraints

1 ≤ arr1.length, arr2.length ≤ 1000
arr1[i] and arr2[i] are 0 or 1
arr1 and arr2 have no leading zeros except when representing 0

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two negabinary arrays representing numbers

Addition Process

Add with proper base -2 carry handling

Result

Sum in negabinary format without leading zeros

Key Takeaway

🎯 Key Insight: Handle carries in base -2 by managing negative powers properly

Asked in

G Google 15 f Facebook 8

The key insight is handling carries properly in base -2 where carrying involves negative powers. The optimal approach simulates binary addition with special carry logic: when sum ≥ 2, carry -1 to next position; when sum < 0, add 2 and carry 1. Time: O(max(n,m)), Space: O(max(n,m)).

Common Approaches

Approach	Time	Space	Notes
✓ Convert to Decimal and Back	O(n + m)	O(1)	Convert both arrays to decimal, add normally, then convert result back to base -2
Simulate Addition with Carry	O(max(n, m))	O(max(n, m))	Directly simulate binary addition with proper carry handling for base -2

Convert to Decimal and Back — Algorithm Steps

Convert arr1 to decimal using negabinary formula
Convert arr2 to decimal using negabinary formula
Add the two decimal numbers
Convert sum back to negabinary array

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert Arrays

Convert both negabinary arrays to decimal

Add Decimals

Perform normal decimal addition

Convert Back

Convert sum back to negabinary format

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long negabinaryToDecimal(int* arr, int size) {
    long long result = 0;
    long long power = 1;
    for (int i = size - 1; i >= 0; i--) {
        result += arr[i] * power;
        power *= -2;
    }
    return result;
}

int* decimalToNegabinary(long long num, int* returnSize) {
    if (num == 0) {
        int* result = (int*)malloc(sizeof(int));
        result[0] = 0;
        *returnSize = 1;
        return result;
    }
    
    int* temp = (int*)malloc(64 * sizeof(int));
    int size = 0;
    
    while (num != 0) {
        if (num % 2 == 0) {
            temp[size++] = 0;
            num /= -2;
        } else {
            temp[size++] = 1;
            num = (num - 1) / -2;
        }
    }
    
    // Reverse and create final result
    int* result = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        result[i] = temp[size - 1 - i];
    }
    
    free(temp);
    *returnSize = size;
    return result;
}

int* solution(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    long long decimal1 = negabinaryToDecimal(arr1, arr1Size);
    long long decimal2 = negabinaryToDecimal(arr2, arr2Size);
    long long total = decimal1 + decimal2;
    
    return decimalToNegabinary(total, returnSize);
}

int main() {
    // Parse input arrays
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,0,1] format
    int arr1[100], arr1Size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        arr1[arr1Size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int arr2[100], arr2Size = 0;
    token = strtok(line, "[,]");
    while (token != NULL) {
        arr2[arr2Size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(arr1, arr1Size, arr2, arr2Size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Converting arrays to decimal takes O(n) and O(m), conversion back takes O(log|result|)

✓ Linear Growth

Space Complexity

O(1)

Only storing decimal values, not counting output array

✓ Linear Space

15.0K Views

Medium Frequency

~25 min Avg. Time

486 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Convert to Decimal and Back — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler