← Static tasks

43. Multiply Strings

leetcode hard

#array#csharp#hard#leetcode#math#string

Task

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"

Output: "6"

C# solution

matched/original
class Solution {
    private List<int> AddStrings(List<int> num1, List<int> num2) {
        List<int> ans = new List<int>();
        int carry = 0;
        for (int i = 0; i < num1.Count || i < num2.Count || carry != 0; ++i) {
            int digit1 = i < num1.Count ? num1[i] : 0;
            int digit2 = i < num2.Count ? num2[i] : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.Add(sum % 10);
        }
        if (carry != 0) {
            ans.Add(carry);
        }
        return ans;
    }
    private List<int> MultiplyOneDigit(StringBuilder firstNumber, char secondNumberDigit, int numZeros) {
        List<int> currentResult = new List<int>(new int[numZeros]);
        int carry = 0;
        for (int i = 0; i < firstNumber.Length; ++i) {
            int multiplication = (secondNumberDigit - '0') * (firstNumber[i] - '0') + carry;
            carry = multiplication / 10;
            currentResult.Add(multiplication % 10);
        }
        if (carry != 0) {
            currentResult.Add(carry);
        }
        return currentResult;
    }
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        StringBuilder firstNumber = new StringBuilder(new string(num1.Reverse().ToArray()));
        StringBuilder secondNumber = new StringBuilder(new string(num2.Reverse().ToArray()));
        int N = firstNumber.Length + secondNumber.Length;
        List<int> ans = new List<int>(new int[N]);
        for (int i = 0; i < secondNumber.Length; ++i) {
            ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
        }
        if (ans[ans.Count - 1] == 0) {
            ans.RemoveAt(ans.Count - 1);
        }
        StringBuilder answer = new StringBuilder();
        for (int i = ans.Count - 1; i >= 0; --i) {
            answer.Append(ans[i]);
        }
        return answer.ToString();
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
    private List<int> AddStrings(List<int> num1, List<int> num2) {
        List<int> ans = new List<int>();
        int carry = 0;
        for (int i = 0; i < num1.size() || i < num2.size() || carry != 0; ++i) {
            int digit1 = i < num1.size() ? num1[i] : 0;
            int digit2 = i < num2.size() ? num2[i] : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.push_back(sum % 10);
        }
        if (carry != 0) {
            ans.push_back(carry);
        }
        return ans;
    }
    private List<int> MultiplyOneDigit(StringBuilder firstNumber, char secondNumberDigit, int numZeros) {
        List<int> currentResult = new List<int>(new int[numZeros]);
        int carry = 0;
        for (int i = 0; i < firstNumber.size(); ++i) {
            int multiplication = (secondNumberDigit - '0') * (firstNumber[i] - '0') + carry;
            carry = multiplication / 10;
            currentResult.push_back(multiplication % 10);
        }
        if (carry != 0) {
            currentResult.push_back(carry);
        }
        return currentResult;
    }
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        StringBuilder firstNumber = new StringBuilder(new string(num1.Reverse().ToArray()));
        StringBuilder secondNumber = new StringBuilder(new string(num2.Reverse().ToArray()));
        int N = firstNumber.size() + secondNumber.size();
        List<int> ans = new List<int>(new int[N]);
        for (int i = 0; i < secondNumber.size(); ++i) {
            ans = AddStrings(MultiplyOneDigit(firstNumber, secondNumber[i], i), ans);
        }
        if (ans[ans.size() - 1] == 0) {
            ans.RemoveAt(ans.size() - 1);
        }
        StringBuilder answer = new StringBuilder();
        for (int i = ans.size() - 1; i >= 0; --i) {
            answer.Append(ans[i]);
        }
        return answer.ToString();
    }
}

Java solution

matched/original
class Solution {
    private ArrayList<Integer> addStrings(
        ArrayList<Integer> num1,
        ArrayList<Integer> num2
    ) {
        ArrayList<Integer> ans = new ArrayList<>();
        int carry = 0;

        for (int i = 0; i < num1.size() || i < num2.size(); ++i) {
            int digit1 = i < num1.size() ? num1.get(i) : 0;
            int digit2 = i < num2.size() ? num2.get(i) : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            ans.add(sum % 10);
        }

        if (carry != 0) {
            ans.add(carry);
        }
        return ans;
    }

    ArrayList<Integer> multiplyOneDigit(
        StringBuilder firstNumber,
        char secondNumberDigit,
        int numZeros
    ) {
        ArrayList<Integer> currentResult = new ArrayList<>();
        for (int i = 0; i < numZeros; ++i) {
            currentResult.add(0);
        }

        int carry = 0;

        for (int i = 0; i < firstNumber.length(); ++i) {
            char firstNumberDigit = firstNumber.charAt(i);
            int multiplication =
                (secondNumberDigit - '0') * (firstNumberDigit - '0') + carry;
            carry = multiplication / 10;
            currentResult.add(multiplication % 10);
        }

        if (carry != 0) {
            currentResult.add(carry);
        }
        return currentResult;
    }

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        StringBuilder firstNumber = new StringBuilder(num1);
        StringBuilder secondNumber = new StringBuilder(num2);

        firstNumber.reverse();
        secondNumber.reverse();

        int N = firstNumber.length() + secondNumber.length();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < N; ++i) {
            ans.add(0);
        }

        for (int i = 0; i < secondNumber.length(); ++i) {
            ans = addStrings(
                multiplyOneDigit(firstNumber, secondNumber.charAt(i), i),
                ans
            );
        }

        if (ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }

        StringBuilder answer = new StringBuilder();

        for (int i = ans.size() - 1; i >= 0; --i) {
            answer.append(ans.get(i));
        }

        return answer.toString();
    }
}

JavaScript solution

matched/original
let addStrings = function (num1, num2) {
    let ans = [];
    let carry = 0;

    for (let i = 0; i < num1.length || i < num2.length; ++i) {
        let digit1 = i < num1.length ? num1[i] : 0;
        let digit2 = i < num2.length ? num2[i] : 0;

        let sum = digit1 + digit2 + carry;
        carry = Math.floor(sum / 10);
        ans.push(sum % 10);
    }

    if (carry) {
        ans.push(carry);
    }
    return ans;
};

let multiplyOneDigit = function (firstNumber, secondNumberDigit, numZeros) {
    let currentResult = [];
    for (let i = 0; i < numZeros; ++i) {
        currentResult.push(0);
    }

    let carry = 0;

    for (let i = 0; i < firstNumber.length; ++i) {
        let multiplication = Number(secondNumberDigit) * Number(firstNumber[i]) + carry;
        carry = Math.floor(multiplication / 10);
        currentResult.push(multiplication % 10);
    }

    if (carry) {
        currentResult.push(carry);
    }
    return currentResult;
};

let multiply = function (num1, num2) {
    if (num1 === "0" || num2 === "0") {
        return "0";
    }

    let firstNumber = [...num1];
    let secondNumber = [...num2];

    firstNumber.reverse();
    secondNumber.reverse();

    let N = firstNumber.length + secondNumber.length;
    let ans = new Array(N).fill(0);

    for (let i = 0; i < secondNumber.length; ++i) {
        ans = addStrings(
            multiplyOneDigit(firstNumber, secondNumber[i], i),
            ans,
        );
    }

    if (ans[ans.length - 1] === 0) {
        ans.pop();
    }

    ans.reverse();
    return ans.join("");
};

Python solution

matched/original
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        first_number = num1[::-1]
        second_number = num2[::-1]

        N = len(first_number) + len(second_number)
        answer = [0] * N

        for index, digit in enumerate(second_number):
            answer = self.addStrings(
                self.multiplyOneDigit(first_number, digit, index), answer
            )

        if answer[-1] == 0:
            answer.pop()

        answer.reverse()
        return "".join(str(digit) for digit in answer)

    def multiplyOneDigit(self, first_number: str, digit2: str, num_zeros: int):
        currentResult = [0] * num_zeros
        carry = 0

        for digit1 in first_number:
            multiplication = int(digit1) * int(digit2) + carry
            carry = multiplication // 10
            currentResult.append(multiplication % 10)

        if carry != 0:
            currentResult.append(carry)
        return currentResult

    def addStrings(self, result: list, answer: list) -> list:
        carry = 0
        new_answer = []
        for digit1, digit2 in zip_longest(result, answer, fillvalue=0):
            curr_sum = digit1 + digit2 + carry
            carry = curr_sum // 10
            new_answer.append(curr_sum % 10)

        return new_answer

Go solution

matched/original
func addStrings(num1 []int, num2 []int) []int {
    ans := []int{}
    carry := 0

    for i := 0; i < len(num1) || i < len(num2) || carry != 0; i++ {
        digit1, digit2 := 0, 0
        if i < len(num1) {
            digit1 = num1[i]
        }
        if i < len(num2) {
            digit2 = num2[i]
        }

        sum := digit1 + digit2 + carry
        carry = sum / 10
        ans = append(ans, sum%10)
    }

    if carry != 0 {
        ans = append(ans, carry)
    }
    return ans
}

func multiplyOneDigit(firstNumber string, secondNumberDigit rune, numZeros int) []int {
    currentResult := make([]int, numZeros)

    carry := 0
    for i := 0; i < len(firstNumber); i++ {
        firstNumberDigit := firstNumber[i] - '0'
        multiplication := int(secondNumberDigit-'0')*int(firstNumberDigit) + carry
        carry = multiplication / 10
        currentResult = append(currentResult, multiplication%10)
    }

    if carry != 0 {
        currentResult = append(currentResult, carry)
    }
    return currentResult
}

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

    firstNumber := reverseString(num1)
    secondNumber := reverseString(num2)

    N := len(firstNumber) + len(secondNumber)
    ans := make([]int, N)

    for i, digit := range secondNumber {
        result := multiplyOneDigit(firstNumber, rune(digit), i)
        ans = addStrings(result, ans)
    }

    if ans[len(ans)-1] == 0 {
        ans = ans[:len(ans)-1]
    }

    var answer strings.Builder
    for i := len(ans) - 1; i >= 0; i-- {
        answer.WriteString(strconv.Itoa(ans[i]))
    }

    return answer.String()
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Explanation

Algorithm

1️⃣

Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:

Инициализируйте переменную carry, первоначально равную 0.

Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2️⃣

Для каждой цифры в firstNumber:

Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.

Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.

Добавьте последнюю цифру в массив currentResult.

Разделите умножение на 10, чтобы получить новое значение для carry.

3️⃣

После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.

Добавьте currentResult к ans.

Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.

Переверните ans и верните его.

😎