Sum of Two Large Numbers (String Representation) ใน C++

โจทย์: บวกเลขใหญ่ 2 ตัวที่เก็บเป็น string (เกิน range ของ built-in types)

ตัวอย่าง: "341299123919" + "52413424" = "341351537343"

อัลกอริธึม: Grade-school Addition

1. Reverse ทั้งสอง string (หรือ traverse จากท้าย)
2. บวก digit by digit + carry 3. เก็บผลลัพธ์ digit ต่อท้าย result string 4. Reverse result กลับ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

string addBigNumbers(string num1, string num2) {
    if (num1.length() > num2.length()) swap(num1, num2);
    string sum = "";
    int n1 = num1.length(), n2 = num2.length();
    int diff = n2 - n1;
    int carry = 0;

    for (int i = n1 - 1; i >= 0; i--) {
        int d1 = num1[i] - '0';
        int d2 = num2[i + diff] - '0';
        int s = d1 + d2 + carry;
        sum.push_back('0' + (s % 10));
        carry = s / 10;
    }
    for (int i = diff - 1; i >= 0; i--) {
        int d2 = num2[i] - '0';
        int s = d2 + carry;
        sum.push_back('0' + (s % 10));
        carry = s / 10;
    }
    if (carry) sum.push_back('0' + carry);
    reverse(sum.begin(), sum.end());
    return sum;
}

int main() {
    string n1 = "235235823852";
    string n2 = "45230820348";
    cout << "Sum: " << addBigNumbers(n1, n2);
}

อินพุต

"235235823852", "45230820348"

เอาต์พุท

280466644200

Complexity

• Time: O(max(N, M))
• Space: O(max(N, M))