Go/Leet Code
[Go] Array and string - Add binary
Gopythor
2022. 4. 3. 20:15
728x90
반응형
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
- 1 <= a.length, b.length <= 104
- a and b consist only of '0' or '1' characters.
- Each string does not contain leading zeros except for the zero itself.
My code
func addBinary(a string, b string) string {
aa := strings.Split(a, "")
bb := strings.Split(b, "")
ans := make([]string, 0)
alen := len(aa) - 1
blen := len(bb) - 1
carry := 0
for alen >= 0 && blen >= 0 {
switch {
case carry == 1:
if aa[alen] == "0" && bb[blen] == "0" {
ans = append([]string{"1"}, ans...)
carry = 0
alen--
blen--
} else if aa[alen] == "1" && bb[blen] == "0" || aa[alen] == "0" && bb[blen] == "1" {
ans = append([]string{"0"}, ans...)
carry = 1
alen--
blen--
} else {
ans = append([]string{"1"}, ans...)
carry = 1
alen--
blen--
}
default:
if aa[alen] == "0" && bb[blen] == "0" {
ans = append([]string{"0"}, ans...)
carry = 0
alen--
blen--
} else if aa[alen] == "1" && bb[blen] == "0" || aa[alen] == "0" && bb[blen] == "1" {
ans = append([]string{"1"}, ans...)
carry = 0
alen--
blen--
} else {
ans = append([]string{"0"}, ans...)
carry = 1
alen--
blen--
}
}
}
if alen >= 0 {
for alen >= 0 {
switch {
case carry == 1:
if aa[alen] == "1" {
ans = append([]string{"0"}, ans...)
carry = 1
alen--
} else if aa[alen] == "0" {
ans = append([]string{"1"}, ans...)
carry = 0
alen--
}
default:
for i := alen; i >= 0; i-- {
ans = append([]string{aa[i]}, ans...)
alen--
}
}
}
} else if blen >= 0 {
for blen >= 0 {
switch {
case carry == 1:
if bb[blen] == "1" {
ans = append([]string{"0"}, ans...)
carry = 1
blen--
} else if bb[blen] == "0" {
ans = append([]string{"1"}, ans...)
carry = 0
blen--
}
default:
for i := blen; i >= 0; i-- {
ans = append([]string{bb[i]}, ans...)
blen--
}
}
}
}
if carry == 1 {
ans = append([]string{"1"}, ans...)
}
return strings.Join(ans, "")
}- I tried to keep binary numbers as string.
- But i don't know why this code takes a lot of memories. I think becasue of prepend.
- Strings will be allocated to array.
- and ans slice will be made.
- length of a and b will be allocated after minus one.
- carry variable will store value when 1 will be handed to next number.
- First for loop will run until alen or blen will be -1.
- In for loop, there is a switch which checks carry is 1 or not.
- If so, a value will be added to slice based on values of a and b.
- carry will be changed also.
- when a or b reches to -1, if condition waits for next step.
- If alen is more than -1, then rest of them will be added to slice.
- during this, carry still works.
- When carry is still 1, 1 will be added to slice to the last of the code
sample 0 ms submission & sample 2300 KB submission
func addBinary(a string, b string) string {
N := len(a)
M := len(b)
nR := max(M,N) + 1
r := make([]rune, nR)
carry := 0
for i:=1 ; i < nR ;i++ {
left, right := 0, 0
if N-i >=0 && a[N-i] == '1' {
left = 1
}
if M-i >=0 && b[M-i] == '1' {
right = 1
}
remain := (left+right+carry) % 2
carry = (left + right + carry) / 2
if remain == 0 {
r[nR-i] = '0'
} else {
r[nR-i] = '1'
}
}
if carry == 1 {
r[0] = '1'
return string(r)
}
return string(r[1:])
}
func max( a, b int) int {
if a > b {
return a
}
return b
}- N and M will have values which are lengthes of a and b.
- r slice which is rune will be made based on max length + 1 of longer one.
- From for loop, End of array will be len -1 so it starts from 1.
- Left and right valuables will have the number which has a and b array.
- First and Second If condition checks it has 1 or not among array.
- remain will have a value which is remainder after adding left and right and carry.
- carry will have a value which is quotient after adding left and right and carry.
- after this, remain value will be allocated to array.
- Last of the code, if condition checks if carry is 1 or not.
- If so, 1 will be allocated to r[0].
- or not it will be returned except r[0]
- Rune is 4 bytes while string is 16 bytes.
- good reference : https://thebook.io/006806/ch03/03/01_02/
- https://darrengwon.tistory.com/1392
Go 언어 웹 프로그래밍 철저 입문: 3.3.1 문자열과 문자 - 2
thebook.io
sample 1 ms submission
func addBinary(a string, b string) string {
c, _ := new(big.Int).SetString(a, 2)
d, _ := new(big.Int).SetString(b, 2)
return fmt.Sprintf("%b", new(big.Int).Add(c, d))
}- So simple Code. I think I should know this way also.
- This code uses math/big package.
- If we use the big.Int and big.Rat types provided by the math/big package, you can use integers and rational numbers without a range limit.
func (z *Int) SetString(s string, base int) (*Int, bool)- when we use octal then put 8 to base argument.
- Add method will return int but Sprint convert int to String.
sample 2 ms submission
func addBinary(str1 string, str2 string) string {
var zero byte = 48
var one byte = 49
if len(str2) > len(str1) {
for len(str1) < len(str2) {
str1 = "0" + str1
}
} else if len(str2) < len(str1) {
for len(str2) < len(str1) {
str2 = "0" + str2
}
}
s3 := make([]byte, len(str1)+1)
cf := false
for i := len(str1) - 1; i >= 0; i-- {
if str1[i] == one && str2[i] == one {
if cf {
s3[i+1] = one
} else {
s3[i+1] = zero
cf = true
}
} else if str1[i] == one || str2[i] == one {
if cf {
s3[i+1] = zero
} else {
s3[i+1] = one
}
} else {
if cf {
s3[i+1] = one
cf = false
} else {
s3[i+1] = zero
}
}
}
if cf {
s3[0] = one
} else {
s3 = s3[1:]
}
return string(s3)
}sample 2100 KB submission
func addBinary(a string, b string) string {
i := len(a)-1
j := len(b)-1
carry := 0
var res []byte
for i >= 0 || j >= 0 || carry > 0 {
sum := carry
carry = 0
if i >= 0 {
if a[i] == '1' {
sum++
}
i--
}
if j >= 0 {
if b[j] == '1' {
sum++
}
j--
}
switch sum {
case 0:
res = append(res, '0')
case 1:
res = append(res, '1')
case 2:
res = append(res, '0')
carry = 1
case 3:
res = append(res, '1')
carry = 1
}
}
for i:=0;i<len(res)/2;i++ {
j := len(res)-i-1
res[i],res[j]=res[j],res[i]
}
return string(res)
}sample 2200 KB submission
func addBinary(a string, b string) string {
return reverse(add(reverse(a), reverse(b)))
}
func reverse(s string) string {
bs := []byte(s)
for i := 0; i < len(bs)/2; i++ {
bs[i], bs[len(bs)-i-1] = bs[len(bs)-i-1], bs[i]
}
return string(bs)
}
func add(a string, b string) string {
cin := byte(0)
res := []byte{}
i := 0
j := 0
for i < len(a) && j < len(b) {
na := a[i]-'0'
nb := b[j]-'0'
s := na ^ nb ^ cin
cin = (na & nb) | (na & cin) | (nb & cin)
res = append(res, s+'0')
i++
j++
}
for i < len(a) {
na := a[i]-'0'
s := na ^ cin
cin = na & cin
res = append(res, s+'0')
i++
}
for j < len(b) {
nb := b[j]-'0'
s := nb ^ cin
cin = nb & cin
res = append(res, s+'0')
j++
}
if cin != 0 {
res = append(res, cin+'0')
}
return string(res)
}sample 2400 KB submission
func addBinary(a string, b string) string {
lenA, lenB := len(a), len(b)
if lenA > lenB {
b = strings.Repeat("0", lenA-lenB) + b
} else if lenB > lenA {
a = strings.Repeat("0", lenB-lenA) + a
lenA = lenB
}
isOne, res := false, make([]string, lenA)
for i := lenA - 1; i >= 0; i-- {
if a[i] == b[i] {
res[i] = "0"
if isOne {
res[i] = "1"
}
isOne = a[i] == '1'
} else if isOne {
res[i] = "0"
} else {
res[i] = "1"
}
}
if isOne {
res = append([]string{"1"}, res...)
}
return strings.Join(res, "")
}sample 2500 KB submission
func addBinary(a string, b string) string {
lenA := len(a)
lenB := len(b)
i := lenA - 1
j := lenB - 1
var output string
var sum int
carry := 0
for i >= 0 && j >= 0 {
first := int(a[i] - '0')
second := int(b[j] - '0')
sum, carry = binarySum(first, second, carry)
output = strconv.Itoa(sum) + output
i = i - 1
j = j - 1
}
for i >= 0 {
first := int(a[i] - '0')
sum, carry = binarySum(first, 0, carry)
output = strconv.Itoa(sum) + output
i = i - 1
}
for j >= 0 {
second := int(b[j] - '0')
sum, carry = binarySum(0, second, carry)
output = strconv.Itoa(sum) + output
j = j - 1
}
if carry > 0 {
output = strconv.Itoa(1) + output
}
return output
}
func binarySum(a, b, carry int) (int, int) {
output := a + b + carry
if output == 0 {
return 0, 0
}
if output == 1 {
return 1, 0
}
if output == 2 {
return 0, 1
}
if output == 3 {
return 1, 1
}
return 0, 0
}sample 2600 KB submission
func addBinary(a string, b string) string {
lenA := len(a)
lenB := len(b)
i := lenA - 1
j := lenB - 1
var output string
var sum int
carry := 0
for i >= 0 && j >= 0 {
first := int(a[i] - '0')
second := int(b[j] - '0')
sum, carry = binarySum(first, second, carry)
output = strconv.Itoa(sum) + output
i = i - 1
j = j - 1
}
for i >= 0 {
first := int(a[i] - '0')
sum, carry = binarySum(first, 0, carry)
output = strconv.Itoa(sum) + output
i = i - 1
}
for j >= 0 {
second := int(b[j] - '0')
sum, carry = binarySum(0, second, carry)
output = strconv.Itoa(sum) + output
j = j - 1
}
if carry > 0 {
output = strconv.Itoa(1) + output
}
return output
}
func binarySum(a, b, carry int) (int, int) {
output := a + b + carry
if output == 0 {
return 0, 0
}
if output == 1 {
return 1, 0
}
if output == 2 {
return 0, 1
}
if output == 3 {
return 1, 1
}
return 0, 0
}728x90
반응형