Welcome to Subscribe On Youtube

1073. Adding Two Negabinary Numbers

Description

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

Solutions

  • 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();
        }
    }
    
  • class Solution {
    public:
        vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
            int i = arr1.size() - 1, j = arr2.size() - 1;
            vector<int> ans;
            for (int c = 0; i >= 0 || j >= 0 || c; --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.push_back(x);
            }
            while (ans.size() > 1 && ans.back() == 0) {
                ans.pop_back();
            }
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };
    
  • 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]
    
    
  • 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
    }
    
  • 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();
    }
    
    
  • public class Solution {
        public int[] AddNegabinary(int[] arr1, int[] arr2) {
            int i = arr1.Length - 1, j = arr2.Length - 1;
            List<int> ans = new List<int>();
            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.Count > 1 && ans[ans.Count - 1] == 0) {
                ans.RemoveAt(ans.Count - 1);
            }
            ans.Reverse();
            return ans.ToArray();
        }
    }
    
    

All Problems

All Solutions