package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/adding-two-negabinary-numbers/
 */
public class Problem1073 {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        boolean positive = true;
        int carry = 0;
        while (i >= 0 && j >= 0) {
            if (positive) {
                int sum = arr1[i] + arr2[j] + carry;
                carry = sum / 2;
                list.add(sum % 2);
                positive = false;
            } else {
                int sum = -(arr1[i] + arr2[j]) + carry;
                carry = sum / 2;
                list.add(Math.abs(sum % 2));
                positive = true;
            }
            i--;
            j--;
        }
        while (i >= 0) {
            if (positive) {
                int sum = arr1[i] + carry;
                carry = sum / 2;
                list.add(sum % 2);
                positive = true;
            } else {
                int sum = -arr1[i] + carry;
                carry = sum / 2;
                list.add(sum % 2);
                positive = false;
            }
            i--;
        }
        while (j >= 0) {
            if (positive) {
                int sum = arr2[j] + carry;
                carry = sum / 2;
                list.add(sum % 2);
                positive = true;
            } else {
                int sum = -arr2[j] + carry;
                carry = sum / -2;
                list.add(sum % 2);
                positive = false;
            }
            j--;
        }
        int size = list.size();
        int k = list.size() - 1;
        while (k >= 0 && list.get(k) == 0) {
            k--;
            size--;
        }
        int[] answer = new int[size];
        int l = 0;
        for (; k >= 0; k--) {
            answer[l++] = list.get(k);
        }
        return answer;
    }

    public static void main(String[] args) {
        Problem1073 prob = new Problem1073();
//        System.out.println(Arrays.toString(prob.addNegabinary(new int[]{1, 1, 1, 1, 1}, new int[]{1, 0, 1}))); // [1,0,0,0,0]
//        System.out.println(Arrays.toString(prob.addNegabinary(new int[]{1, 1, 1, 1, 1}, new int[]{1, 0, 1, 1}))); // [1,1,0]
//        System.out.println(Arrays.toString(prob.addNegabinary(new int[]{1, 1, 1, 1, 1, 0, 1}, new int[]{1, 0, 1, 1, 1, 1, 0}))); // [1,1,0,0,0,1,0,1,1]
        System.out.println(Arrays.toString(prob.addNegabinary(new int[]{1, 0}, new int[]{1, 0}))); // [1,1,0,0]
    }
}

@@ -603,42 +603,8 @@
 2);%0A
-                positive = false;%0A
     
@@ -754,24 +754,34 @@
  %25 2));%0A    
+        %7D%0A
             
@@ -791,35 +791,26 @@
 itive = 
-true;%0A            %7D
+!positive;
 %0A       
@@ -838,32 +838,279 @@
  j--;%0A        %7D%0A
+        if (i %3C 0 && j %3C 0) %7B%0A            while (carry != 0) %7B%0A                int sum = carry;%0A                carry = sum / 2;%0A                list.add(Math.abs(sum %25 2));%0A                positive = !positive;%0A            %7D%0A        %7D else %7B%0A    
         while (i
@@ -1122,32 +1122,36 @@
 ) %7B%0A            
+    
 if (positive) %7B%0A
@@ -1158,32 +1158,36 @@
                 
+   
+ 
 int sum = arr1%5Bi
@@ -1205,32 +1205,36 @@
                 
+    
 carry = sum / 2;
@@ -1242,32 +1242,36 @@
                 
+  
+  
 list.add(sum %25 2
@@ -1281,37 +1281,8 @@
     
-            positive = true;%0A
     
@@ -1290,32 +1290,36 @@
        %7D else %7B%0A
+    
                 
@@ -1354,32 +1354,36 @@
                 
+    
 carry = sum / 2;
@@ -1375,32 +1375,36 @@
 arry = sum / 2;%0A
+    
                 
@@ -1414,32 +1414,50 @@
 t.add(sum %25 2);%0A
+                %7D%0A
                 
@@ -1467,37 +1467,31 @@
 itive = 
-fals
+!positiv
 e;%0A    
-        %7D%0A
         
@@ -1499,34 +1499,42 @@
    i--;%0A        
-%7D%0A
+    %7D%0A    
         while (j
@@ -1546,32 +1546,36 @@
 ) %7B%0A            
+    
 if (positive) %7B%0A
@@ -1582,32 +1582,36 @@
                 
+  
+  
 int sum = arr2%5Bj
@@ -1629,32 +1629,36 @@
                 
+    
 carry = sum / 2;
@@ -1666,32 +1666,36 @@
                 
+ 
+   
 list.add(sum %25 2
@@ -1705,37 +1705,8 @@
     
-            positive = true;%0A
     
@@ -1714,32 +1714,36 @@
        %7D else %7B%0A
+    
                 
@@ -1778,32 +1778,36 @@
                 
+    
 carry = sum / -2
@@ -1808,16 +1808,20 @@
 m / -2;%0A
+    
         
@@ -1839,32 +1839,50 @@
 t.add(sum %25 2);%0A
+                %7D%0A
                 
@@ -1896,12 +1896,16 @@
 e = 
-fals
+!positiv
 e;%0A 
@@ -1907,33 +1907,40 @@
 ve;%0A            
-%7D
+    j--;
 %0A            j--
@@ -1928,36 +1928,33 @@
 --;%0A            
-j--;
+%7D
 %0A        %7D%0A     

Update problem 1073