Длинная арифметика

В этом уроке ты

Решишь задачу с собеседования в BigTech
Научишься решать задачу, которая не попадает под основные паттерны решения, от чего и может вызывать трудности.

Ты на собеседовании

Представь, что ты на собеседовании. У тебя есть 20 минут, чтобы придумать решение задачи!

Условие

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

Даны два непустых массива nums1 и nums2, где каждый элемент — это цифра (от 0 до 9). Эти массивы представляют собой длинные числа. Твоя задача — написать логику их сложения. Учитывай, что 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

В чем сложность задачи?

Главная сложность — найти подход к задаче и придумать лаконичное решение.

Рассмотрим подход, основанный на выравнивании длин массивов путем добавления ведущих нулей, после чего производится посимвольное сложение их элементов.

using System;
using System.Collections.Generic;

public class Solution
{
    // Время: O(max(n,m)), где n - размер nums1, m - размер nums2
    // Память: O(max(n,m))
    public static List<int> Calculate(List<int> nums1, List<int> nums2)
    {
        // Выравниваем длины массивов, заполняя ведущими нулями
        int maxLen = Math.Max(nums1.Count, nums2.Count);
        nums1.InsertRange(0, new int[maxLen - nums1.Count]);
        nums2.InsertRange(0, new int[maxLen - nums2.Count]);

        // Инициализация переменных для сложения
        int carry = 0;
        List<int> result = new List<int>();

        // Проходимся по числам справа налево
        for (int i = maxLen - 1; i >= 0; --i)
        {
            int digitSum = nums1[i] + nums2[i] + carry;
            carry = digitSum / 10;  // Сохраняем перенос
            result.Add(digitSum % 10);  // Оставляем только текущую цифру
        }

        // Если после последнего сложения остался перенос, добавляем его
        if (carry > 0)
        {
            result.Add(carry);
        }

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

#include <vector>
#include <algorithm> // для std::max и std::reverse

using namespace std;

// Время: O(max(n,m)), где n - размер nums1, m - размер nums2
// Память: O(max(n,m))
vector<int> calculate(vector<int>& nums1, vector<int>& nums2) {
    // Выравниваем длины массивов, заполняя ведущими нулями
    int max_len = max(nums1.size(), nums2.size());
    nums1.insert(nums1.begin(), max_len - nums1.size(), 0);
    nums2.insert(nums2.begin(), max_len - nums2.size(), 0);

    // Инициализация переменных для сложения
    int carry = 0;
    vector<int> result;

    // Проходимся по числам справа налево
    for (int i = max_len - 1; i >= 0; --i) {
        int digit_sum = nums1[i] + nums2[i] + carry;
        carry = digit_sum / 10;  // Сохраняем перенос
        result.push_back(digit_sum % 10);  // Оставляем только текущую цифру
    }

    // Если после последнего сложения остался перенос, добавляем его
    if (carry > 0) {
        result.push_back(carry);
    }

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

package main

import "math"

// Время: O(max(n,m)), где n - размер nums1, m - размер nums2
// Память: O(max(n,m))
func calculate(nums1 []int, nums2 []int) []int {
    // Выравниваем длины массивов, заполняя ведущими нулями
    maxLen := int(math.Max(float64(len(nums1)), float64(len(nums2))))
    nums1 = append(make([]int, maxLen-len(nums1)), nums1...)
    nums2 = append(make([]int, maxLen-len(nums2)), nums2...)

    // Инициализация переменных для сложения
    carry := 0
    result := []int{}

    // Проходимся по числам справа налево
    for i := maxLen - 1; i >= 0; i-- {
        digitSum := nums1[i] + nums2[i] + carry
        carry = digitSum / 10 // Сохраняем перенос
        result = append(result, digitSum%10) // Оставляем только текущую цифру
    }

    // Если после последнего сложения остался перенос, добавляем его
    if carry > 0 {
        result = append(result, carry)
    }

    // Результат в обратном порядке, разворачиваем его обратно
    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 {
    // Время: O(max(n,m)), где n - размер nums1, m - размер nums2
    // Память: O(max(n,m))
    public static List<Integer> calculate(List<Integer> nums1, List<Integer> nums2) {
        // Выравниваем длины массивов, заполняя ведущими нулями
        int maxLen = Math.max(nums1.size(), nums2.size());
        while (nums1.size() < maxLen) {
            nums1.add(0, 0); // Добавляем ведущий ноль
        }
        while (nums2.size() < maxLen) {
            nums2.add(0, 0); // Добавляем ведущий ноль
        }

        // Инициализация переменных для сложения
        int carry = 0;
        List<Integer> result = new ArrayList<>();

        // Проходимся по числам справа налево
        for (int i = maxLen - 1; i >= 0; i--) {
            int digitSum = nums1.get(i) + nums2.get(i) + carry;
            carry = digitSum / 10;  // Сохраняем перенос
            result.add(digitSum % 10);  // Оставляем только текущую цифру
        }

        // Если после последнего сложения остался перенос, добавляем его
        if (carry > 0) {
            result.add(carry);
        }

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

from typing import *

# Время: O(max(n,m)), где n - размер nums1, m - размер nums2
# Память:  O(max(n,m))
def calculate(nums1: List[int], nums2: List[int]) -> List[int]:
    # Выравниваем длины массивов, заполняя ведущими нулями
    max_len = max(len(nums1), len(nums2))
    nums1 = [0] * (max_len - len(nums1)) + nums1
    nums2 = [0] * (max_len - len(nums2)) + nums2

    # Инициализация переменных для сложения
    carry = 0
    result = []

    # Проходимся по числам справа налево
    for i in range(max_len - 1, -1, -1):
        digit_sum = nums1[i] + nums2[i] + carry
        carry = digit_sum // 10  # Сохраняем перенос
        result.append(digit_sum % 10)  # Оставляем только текущую цифру

    # Если после последнего сложения остался перенос, добавляем его
    if carry > 0:
        result.append(carry)

    # Результат в обратном порядке, разворачиваем его обратно
    result.reverse()
    return result

function calculate(nums1, nums2) {
    // Время: O(max(n,m)), где n - размер nums1, m - размер nums2
    // Память: O(max(n,m))

    // Выравниваем длины массивов, заполняя ведущими нулями
    const maxLen = Math.max(nums1.length, nums2.length);
    nums1 = Array(maxLen - nums1.length).fill(0).concat(nums1);
    nums2 = Array(maxLen - nums2.length).fill(0).concat(nums2);

    // Инициализация переменных для сложения
    let carry = 0;
    const result = [];

    // Проходимся по числам справа налево
    for (let i = maxLen - 1; i >= 0; i--) {
        const digitSum = nums1[i] + nums2[i] + carry;
        carry = Math.floor(digitSum / 10); // Сохраняем перенос
        result.push(digitSum % 10); // Оставляем только текущую цифру
    }

    // Если после последнего сложения остался перенос, добавляем его
    if (carry > 0) {
        result.push(carry);
    }

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

Этот метод не является оптимальным, так как изменяет входные данные, что зачастую может противоречить условию задачи.

Оптимальное решение

Рассмотри, оптимальное решение (в комментариях довольно подробно расписано что, зачем и почему).

using System;
using System.Collections.Generic;

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;
            // если overallSum = 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();
}

Основная идея:

Входящие массивы обходим с конца.
Результат собираем последовательно, не забывая переносить разряд.
Если какой-то из курсоров вышел за пределы, берём 0.
Цикл повторяем до тех пор, пока не исчерпали оба массива и есть что переносить.
Результат получается в обратном порядке, поэтому нужно его развернуть.

Оценка по времени и памяти

Время: O(max(n,m)), где n - размер nums1, m - размер nums2
Память: O(max(n,m))

Тут всё просто, двигаемся пока не пройдем полностью массивы, т.е пока не дойдем до конца самого длинного. Если строго, то max(n,m)+1 , но в Big-O опускаем единицу. И память также O(max(n,m)), поскольку выделяется под результирующий массив.

Что дальше

Вперед к задачкам! Решать и решать. Только через практику можно прийти к успеху.