{"id":5225,"date":"2019-06-06T22:10:38","date_gmt":"2019-06-07T05:10:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5225"},"modified":"2019-06-06T22:11:04","modified_gmt":"2019-06-07T05:11:04","slug":"leetcode-1073-adding-two-negabinary-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1073-adding-two-negabinary-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1073. Adding Two Negabinary Numbers"},"content":{"rendered":"\n

Given two numbers arr1<\/code> and arr2<\/code> in base -2<\/strong>, return the result of adding them together.<\/p>\n\n\n\n

Each number is given in array format<\/em>:  as an array of 0s and 1s, from most significant bit to least significant bit.  For example, arr = [1,1,0,1]<\/code> represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3<\/code>.  A number arr<\/code> in array format<\/em> is also guaranteed to have no leading zeros: either arr == [0]<\/code> or arr[0] == 1<\/code>.<\/p>\n\n\n\n

Return the result of adding arr1<\/code> and arr2<\/code> in the same format: as an array of 0s and 1s with no leading zeros.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>arr1 = [1,1,1,1,1], arr2 = [1,0,1]\nOutput: <\/strong>[1,0,0,0,0]\nExplanation: <\/strong>arr1 represents 11, arr2 represents 5, the output represents 16.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= arr1.length <= 1000<\/code><\/li>
  2. 1 <= arr2.length <= 1000<\/code><\/li>
  3. arr1<\/code> and arr2<\/code> have no leading zeros<\/li>
  4. arr1[i]<\/code> is 0<\/code> or 1<\/code><\/li>
  5. arr2[i]<\/code> is 0<\/code> or 1<\/code><\/li><\/ol>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, 8 ms, 9.2 MB\nclass Solution {\npublic:\n  vector addNegabinary(vector& arr1, vector& arr2) {\n    int i = arr1.size();\n    int j = arr2.size();\n    int carry = 0;\n    vector ans;\n    while (i || j || carry) {\n      int sum =  (i ? arr1[--i] : 0) + (j ? arr2[--j] : 0) + carry;      \n      ans.push_back(sum & 1);\n      carry = -(sum >> 1);\n    }\n    while (ans.back() == 0 && ans.size() > 1) ans.pop_back();\n    reverse(begin(ans), end(ans));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[16,179],"class_list":["post-5225","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-bit","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5225","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5225"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5225\/revisions"}],"predecessor-version":[{"id":5227,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5225\/revisions\/5227"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}