[MEDIUM] #1074 - Number of Submatrices That Sum to Target

[hackdartstorm]

🎯 Problem: Adding Two Negabinary Numbers

📖 The Real Problem

You are given two numbers represented in negabinary (base -2) notation as arrays of bits (0s and 1s). Your task is to add these two numbers and return the result also in negabinary form.

What is Negabinary?

• Base -2 number system (not base 2!)
• Each position represents (-2)^power instead of 2^power
• Position values: 1, -2, 4, -8, 16, -32, ... (alternating signs)
• Example: [1,1,0,1] = 1×(-2)³ + 1×(-2)² + 0×(-2)¹ + 1×(-2)⁰ = -8 + 4 + 0 + 1 = -3

The Challenge:

• Addition rules differ from binary (carries can be negative!)
• Need to handle negative carries correctly
• Result must be in canonical form (no leading zeros except for [0])
• Must work for both positive and negative results

Why this problem exists:

• Tests understanding of non-standard number systems
• Requires adapting familiar algorithms to new rules
• Builds mathematical flexibility

💡 Why This Matters

Real-world applications:

• Computer Arithmetic - Alternative number representations
• Error-Correcting Codes - Negabinary has useful properties
• Cryptography - Unusual number systems for encryption
• Mathematical Education - Understanding number system fundamentals

Skills you'll develop:

• ✅ Non-standard base arithmetic
• ✅ Carry propagation with negative bases
• ✅ Array manipulation
• ✅ Mathematical reasoning
• ✅ Algorithm adaptation

📋 Contributor Tasks

Step 1: Understand Negabinary

1. Learn how base -2 works
2. Practice converting decimal to negabinary
3. Practice converting negabinary to decimal
4. Understand carry rules for base -2

Step 2: Plan Your Approach

Key Insight:
When adding in base -2:

• Sum can be 0, 1, 2, or 3
• If sum ≥ 2, we need to carry
• Carry rule: carry = -1 when we have 2 or 3

Addition Rules:

• 0 + 0 = 0, carry 0
• 0 + 1 = 1, carry 0
• 1 + 0 = 1, carry 0
• 1 + 1 = 0, carry -1 (because 2 in base -2 = 110)
• With carry: adjust accordingly

Step 3: Implement the Solution

1. Start from rightmost bits (least significant)
2. Add bits from both arrays plus carry
3. Calculate result bit and new carry
4. Handle remaining carry after all bits processed
5. Remove leading zeros
6. Return result

Step 4: Test Your Solution

1. Test with simple addition: 1 + 1
2. Test with different lengths
3. Test with result = 0
4. Test with negative result
5. Test with leading zeros in input

✅ Expected Outcome

Function Signature:

def addNegabinary(arr1, arr2):
    """
    Add two negabinary (base -2) numbers.
    
    Args:
        arr1: List[int] - first negabinary number (array of bits)
        arr2: List[int] - second negabinary number (array of bits)
    
    Returns:
        List[int]: sum in negabinary form
    
    Example:
        >>> addNegabinary([1], [1])
        [1, 1, 0]  # 1 + 1 = 2 in decimal = 110 in negabinary
    """

Expected Behavior:

• ✅ Returns sum in negabinary (base -2)
• ✅ No leading zeros (except [0] for zero)
• ✅ Handles different length inputs
• ✅ Works for positive and negative results
• ✅ Correct carry propagation

Example Test Cases:

# Test 1: Simple addition
addNegabinary([1], [1])  # Returns: [1, 1, 0]
# Explanation: 1 + 1 = 2 (decimal) = 110 (negabinary)

# Test 2: Different lengths
addNegabinary([1, 0, 1], [1])  # Returns: [0, 0, 1]
# Explanation: -3 + 1 = -2 (decimal) = 100 (negabinary)

# Test 3: Result is zero
addNegabinary([1, 1], [1, 1])  # Returns: [0]
# Explanation: -1 + -1 = -2... wait, need to verify

# Test 4: With carries
addNegabinary([1, 1, 1], [1, 0, 1])  # Returns: [1, 0, 0, 0]
# Verify by converting to decimal

# Test 5: Leading zeros in input
addNegabinary([0, 0, 1], [1])  # Returns: [1, 1, 0]
# Should handle and remove leading zeros

📚 Additional Context & References

Understanding Negabinary

Base -2 Position Values:

Position:  4    3    2    1    0
Value:    16   -8    4   -2    1

Conversion Examples:

Decimal 3 = 111 (negabinary)
= 1×4 + 1×(-2) + 1×1 = 4 - 2 + 1 = 3

Decimal -3 = 1101 (negabinary)
= 1×(-8) + 1×4 + 0×(-2) + 1×1 = -8 + 4 + 0 + 1 = -3

Decimal 2 = 110 (negabinary)
= 1×4 + 1×(-2) + 0×1 = 4 - 2 = 2

Solution Approach

Standard Algorithm:

def addNegabinary(arr1, arr2):
    result = []
    carry = 0
    i, j = len(arr1) - 1, len(arr2) - 1
    
    while i >= 0 or j >= 0 or carry != 0:
        # Get current bits
        bit1 = arr1[i] if i >= 0 else 0
        bit2 = arr2[j] if j >= 0 else 0
        
        # Add bits and carry
        total = bit1 + bit2 + carry
        
        # Result bit is total % 2 (always 0 or 1)
        result.append(total & 1)
        
        # Carry calculation for base -2
        # If total >= 2, we need to carry -1
        carry = -(total >> 1)
        
        i -= 1
        j -= 1
    
    # Remove leading zeros
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    return result[::-1]  # Reverse to get correct order

Hints (Use Only If Stuck!)

💡 Hint 1

Think about what happens when you add 1 + 1 in base -2. What should the carry be?

💡 Hint 2

The carry in base -2 can be negative. When you have a sum of 2, the carry is -1.

💡 Hint 3

Process from right to left like regular addition, but with different carry rules.

Complexity Analysis

Time Complexity: O(max(n, m))

• n = length of arr1, m = length of arr2
• Single pass through both arrays
• Carry propagation is constant time per position

Space Complexity: O(max(n, m))

• Result array size proportional to input size
• May be one digit longer due to final carry

Related Problems

Once you solve this, try:

• Add Binary - Standard base 2 addition
• Add Strings - String-based addition
• Multiply Strings - More complex arithmetic
• Convert to Base -2 - Conversion problem

Helpful Resources

• Negabinary System
• Base -2 Calculator
• LeetCode 1073 - Adding Two Negabinary Numbers

📝 Notes

• Input arrays contain only 0s and 1s
• No leading zeros in input (except [0])
• Output should have no leading zeros (except [0])
• Arrays are in big-endian order (most significant bit first)
• Length: 1 to 40 bits
• Result fits within reasonable integer range

---

Ready to contribute?

1. Fork the repository
2. Create your solution file
3. Test with provided examples
4. Submit a pull request!

File Location: exercises/1000_programs/medium/1073_adding_negabinary_numbers.py

🚀 Happy coding!