Leetcode 1073. Adding Two Negabinary Numbers

Posted on In ,

题目描述

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 <= 1000
  • arr1[i] and arr2[i] are 0 or 1
  • arr1 and arr2 have no leading zeros

解答

The idea is to simply emulate the procedure of addition and carry. And the following two Big Endian equations show the property of addition in base -2.

  • \([-1]=[1, 1]\)
  • \([2]=[-1,0]=[1,1,0]\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        vector<int> tmp(max(arr1.size(),arr2.size())+2,0);
        int ptr=0;
        for (int i=arr1.size()-1;i>=0;i--){
            tmp[ptr]+=arr1[i];
            ptr++;
        }
        ptr=0;
        for (int i=arr2.size()-1;i>=0;i--){
            tmp[ptr]+=arr2[i];
            ptr++;
        }
        for (int i=0;i<=tmp.size()-1;i++){
            if (!(tmp[i]==0 || tmp[i]==1)){
                if (tmp[i]>=2){
                    tmp[i]-=2;
                    tmp[i+1]-=1;
                }
                else if (tmp[i]==-1){
                    tmp[i]=1;
                    tmp[i+1]+=1;
                }
            }
        }
        vector<int> ans;
        bool save=false;
        for (int i=(int)tmp.size()-1;i>=0;i--){
            if (tmp[i]==1){
                save=true;
            }
            if (i==0){
                save=true;
            }
            if (save){
                ans.push_back(tmp[i]);
            }
        }
        return ans;
    }
};

Complexity

  • Time: \(O(N)\)
  • Space: \(O(N)\) including I/O space.

题外话

In C++ standard library, the function size(), which is to get the size of a container, outputs an unsigned integer value.