План курса / Все задачи / Алгоритмы и структуры данных

Сложение длинных чисел

средне

# решено

Не всегда достаточно типа int или даже int64 для сложения чисел. Порой числа настолько большие, что просто не помещаются в базовые типы.

Даны массивы nums1 и nums2, где каждый массив представляет собой длинное число. Необходимо самому написать логику сложения. Учитывай, что nums1 и nums2 могут быть очень длинными.

Пример 1:

Ввод: nums1 = [1,2,3], nums2 = [4,5,6]
Вывод: [5,7,9]
Объяснение: 123 + 456 = 579

Пример 2:

Ввод: nums1 = [9,9,9], nums2 = [9]
Вывод: [1,0,0,8]
Объяснение: 999 + 9 = 1008

Ограничения:

len(nums1) >= 1
len(nums2) >= 1
0 <= nums1[i] <= 9
0 <= nums2[i] <= 9

public class Solution
{
    public static List<int> Calculate(List<int> nums1, List<int> nums2)
    {
        List<int> result = new List<int>();
        // carry - число, которое переносим в следующий разряд
        int carry = 0;

        // складываем числа с конца, поэтому указатели ставим на конец
        // и двигаем в начало строки
        int p1 = nums1.Count - 1;
        int p2 = nums2.Count - 1;

        while (p1 >= 0 || p2 >= 0 || carry > 0)
        {
            // если выходим за границу массива, то текущее число
            // для сложения это 0, иначе достаем значение из массива
            int num1 = (p1 >= 0) ? nums1[p1] : 0;
            int num2 = (p2 >= 0) ? nums2[p2] : 0;

            // вычисляем сумму двух чисел и carry
            int overallSum = num1 + num2 + carry;
            // если overall_sum = 17, то carry = 1,
            // а 7 должна быть записана в текущий разряд ответа
            carry = overallSum / 10;
            result.Add(overallSum % 10);

            // сдвигаем указатели к следующему разряду
            p1--;
            p2--;
        }

        // результат получился в обратном порядке, поэтому нужно развернуть
        result.Reverse();
        return result;
    }
}

#include <vector>

using namespace std;

vector<int> calculate(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> result;
    // carry - число, которое переносим в следующий разряд
    int carry = 0;

    // складываем числа с конца, поэтому указатели ставим на конец
    // и двигаем в начало строки
    int p1 = nums1.size() - 1;
    int p2 = nums2.size() - 1;

    while (p1 >= 0 || p2 >= 0 || carry > 0) {
        // если выходим за границу массива, то текущее число
        // для сложения это 0, иначе достаем значение из массива
        int num1 = (p1 >= 0) ? nums1[p1] : 0;
        int num2 = (p2 >= 0) ? nums2[p2] : 0;

        // вычисляем сумму двух чисел и carry
        int overall_sum = num1 + num2 + carry;
        // если overall_sum = 17, то carry = 1,
        // а 7 должна быть записана в текущий разряд ответа
        carry = overall_sum / 10;
        result.push_back(overall_sum % 10);

        // сдвигаем указатели к следующему разряду
        p1--;
        p2--;
    }

    // результат получился в обратном порядке, поэтому нужно развернуть
    reverse(result.begin(), result.end());
    return result;
}

package main

func calculate(nums1 []int, nums2 []int) []int {
    result := []int{}
    // carry - число, которое переносим в следующий разряд
    carry := 0

    // складываем числа с конца, поэтому указатели ставим на конец
    // и двигаем в начало строки
    p1 := len(nums1) - 1
    p2 := len(nums2) - 1

    for p1 >= 0 || p2 >= 0 || carry > 0 {
        // если выходим за границу массива, то текущее число
        // для сложения это 0, иначе достаем значение из массива
        num1, num2 := 0, 0
        if p1 >= 0 {
            num1 = nums1[p1]
        }
        if p2 >= 0 {
            num2 = nums2[p2]
        }

        // вычисляем сумму двух чисел и carry
        overallSum := num1 + num2 + carry
        // если overall_sum = 17, то carry = 1,
        // а 7 должна быть записана в текущий разряд ответа
        carry = overallSum / 10
        result = append(result, overallSum % 10)

        // сдвигаем указатели к следующему разряду
        p1--
        p2--
    }

    // результат получился в обратном порядке, поэтому нужно развернуть
    for i, j := 0, len(result) - 1; i < j; i, j = i + 1, j - 1 {
        result[i], result[j] = result[j], result[i]
    }
    return result
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {

    public List<Integer> calculate(List<Integer> nums1, List<Integer> nums2) {
        List<Integer> result = new ArrayList<>();
        // carry - число, которое переносим в следующий разряд
        int carry = 0;

        // складываем числа с конца, поэтому указатели ставим на конец
        // и двигаем в начало строки
        int p1 = nums1.size() - 1;
        int p2 = nums2.size() - 1;

        while (p1 >= 0 || p2 >= 0 || carry > 0) {
            // если выходим за границу массива, то текущее число
            // для сложения это 0, иначе достаем значение из массива
            int num1 = (p1 >= 0) ? nums1.get(p1) : 0;
            int num2 = (p2 >= 0) ? nums2.get(p2) : 0;

            // вычисляем сумму двух чисел и carry
            int overallSum = num1 + num2 + carry;
            // если overall_sum = 17, то carry = 1,
            // а 7 должна быть записана в текущий разряд ответа
            carry = overallSum / 10;
            result.add(overallSum % 10);

            // сдвигаем указатели к следующему разряду
            p1--;
            p2--;
        }

        // результат получился в обратном порядке, поэтому нужно развернуть
        Collections.reverse(result);
        return result;
    }
}

from typing import *

def calculate(nums1: List[int], nums2: List[int]) -> List[int]:
    result = []
    # carry - число, которое переносим в следующий разряд
    carry = 0

    # складываем числа с конца, поэтому указатели ставим на конец
    # и двигаем в начало строки
    p1 = len(nums1) - 1
    p2 = len(nums2) - 1
    while p1 >= 0 or p2 >= 0 or carry > 0:
        # если выходим за границу массива, то текущее число
        # для сложения это 0, иначе достаем значение из массива
        num1, num2 = 0, 0
        if p1 >= 0:
            num1 = nums1[p1]
        if p2 >= 0:
            num2 = nums2[p2]
        
        # вычисляем сумму двух чисел и carry
        overall_sum = num1 + num2 + carry
        # если overall_sum = 17, то carry = 1,
        # a 7 должна быть записана в текущий разряд ответа
        carry = overall_sum // 10
        result.append(overall_sum % 10)

        # сдвигаем указатели к следующему разряду
        p1 -= 1
        p2 -= 1
    # результат получился в обратном порядке, поэтому нужно развернуть
    return list(reversed(result))

export function calculate(nums1, nums2) {
    const result = [];
    // carry - число, которое переносим в следующий разряд
    let carry = 0;

    // складываем числа с конца, поэтому указатели ставим на конец
    // и двигаем в начало строки
    let p1 = nums1.length - 1;
    let p2 = nums2.length - 1;

    while (p1 >= 0 || p2 >= 0 || carry > 0) {
        // если выходим за границу массива, то текущее число
        // для сложения это 0, иначе достаем значение из массива
        let num1 = 0;
        let num2 = 0;

        if (p1 >= 0) {
            num1 = nums1[p1];
        }
        if (p2 >= 0) {
            num2 = nums2[p2];
        }

        // вычисляем сумму двух чисел и carry
        const overallSum = num1 + num2 + carry;
        // если overall_sum = 17, то carry = 1,
        // а 7 должна быть записана в текущий разряд ответа
        carry = Math.floor(overallSum / 10);
        result.push(overallSum % 10);

        // сдвигаем указатели к следующему разряду
        p1 -= 1;
        p2 -= 1;
    }
    // результат получился в обратном порядке, поэтому нужно развернуть
    return result.reverse();
}

Оценка сложности

Время: O(max(n,m)), где n - длина массива nums1; m - длина массива nums2
Память: O(max(n,m)), где n - длина массива nums1; m - длина массива nums2