Array
Math
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
Solution 1
Python3 Java C++ Go TypeScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 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 ]
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 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 ();
}
}
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 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 ;
}
};
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 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 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 ();
}
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 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 ();
}
}
GitHub