[Go] Array and string - Add binary

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

 

 

 

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
}