This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

String addition

Given two non-negative integers num1 and num2 in the form of strings, compute their sum.

Tip:

  1. num1 和num2Are all less than 5100
  2. num1 和num2All contain only numbers0-9
  3. num1 和num2None of them contain any leading zeros
  4. You cannot use any of the built-in BigInteger libraries, nor can you directly convert an input string to an integer

Problem solving:

This problem does not allow the conversion of string to integer, we can use vertical operations to achieve bit-by-bit addition (grade 1).

  1. If you add the same bits, if you add different lengths, that’s the same thing as adding the long bits to the 0.
  2. If you add the two digits, you get more than 10. You go one place down.

The time complexity is determined by the length of the string, O(Max (n1, n2)).

The code is as follows:

func addStrings(num1 string, num2 string) string {
    var toNext int      / / carry
    var ans string
    i := len(num1) - 1
    j := len(num2) - 1
    for i >= 0 || j >= 0|| toNext ! =0 {
        var x, y int
        if i >= 0 {
            x = int(num1[i] - '0')}if j >= 0 {
            y = int(num2[j] - '0')
        }
        temp := x + y + toNext
        ans = strconv.Itoa(temp%10) + ans
        toNext = temp / 10

        i--
        j--
    }
    return ans
}
Copy the code

Submission Results:

String multiplication

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, whose product is also represented as strings.

Description:

  1. num1 和 num2The length is less than 110.
  2. num1 和 num2Contains only numbers0-9.
  3. num1 和 num2None begins with a zero, except the number 0 itself.
  4. You cannot process it using any of the standard library large number types (such as BigInteger) or by converting the input directly to an integer.

Problem solving:

So we’re going to do the same thing, and we can do the same thing with the vertical calculation.

Multiply each character of the string like the code above.

In the above addition operation, there is a one-to-one correspondence between the digits, while in the multiplication operation, each digit is multiplied, and the time complexity of all multiplication operations is O(n1 * n2).

Add all the numbers obtained by multiplication to the “0” of the corresponding digit (obtained by summing the pointer digits traversing NUM1 and num2 (counting from 0)). Add all the numbers above, so the time complexity is O(Max (n1, n2) * (n1 + n2)).

Code implementation:

func multiply(num1 string, num2 string) string {
   if num1 == "0" || num2 == "0" {
      return "0"
   }

   var ans string
   for i := len(num1) - 1; i >= 0; i-- {
      for j := len(num2) - 1; j >= 0; j-- {
         x := int(num1[i] - '0')
         y := int(num2[j] - '0')
         if x * y == 0 {
            continue
         }
         temp := strconv.Itoa(x * y)
         for t := 0; t < len(num1) + len(num2) - (i + j + 2); t++ {
            temp += "0"
         }
         ans = addStrings(ans, temp)
      }
   }
   return ans
}
Copy the code
  • The addition code is up here.