Home
C++ Algorithm to Add Two Big Integers (of String Type)
Tags:, ,

C++ Algorithm to Add Two Big Integers (of String Type)

November 8, 2020 No Comments algorithms, c / c++, math, string

Given two strings a, and b, both representing an integer, add them and return it in the same string representation.

Bonus: can you implement the addition directly, instead of using eval or built-in big integers?

Constraints
n ≤ 200 where n is the length of a
m ≤ 200 where m is the length of b
Example 1
Input

a = “12”
b = “23”
Output

“35”
Explanation
12 + 23 = 35

Algorithms to Add Two Big Integers

To add two big integers, we need to start from the least significant digits (rightmost) and then carry over the digit sums. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

string solve(string a, string b) {
    int c = 0;
    int la = a.size() - 1;
    int lb = b.size() - 1;
    string ans = "";
    while ((la >= 0) || (lb >= 0) || (c > 0)) {
        int v = c;
        if (la >= 0) v += a[la --] - '0';
        if (lb >= 0) v += b[lb --] - '0';
        ans = ((char)(48 + v % 10)) + ans;
        c = v/10;
    }
    return ans;
}
string solve(string a, string b) {
    int c = 0;
    int la = a.size() - 1;
    int lb = b.size() - 1;
    string ans = "";
    while ((la >= 0) || (lb >= 0) || (c > 0)) {
        int v = c;
        if (la >= 0) v += a[la --] - '0';
        if (lb >= 0) v += b[lb --] - '0';
        ans = ((char)(48 + v % 10)) + ans;
        c = v/10;
    }
    return ans;
}

The above C++ only uses one while loop – at the cost of checking three conditions each iteration. You can solve this puzzle using eval or BigInteger class, or in Python easily.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
278 words
Last Post: NUC: All-In-One Raspberry PI 400 Kit - Personal Computer Kit with Raspbian OS
Next Post: C++ Run-Length Decoding Algorithm

The Permanent URL is: C++ Algorithm to Add Two Big Integers (of String Type)

Related posts:

  1. Two Pointer and Sliding Window Algorithm to Find K-Length Substrings With No Repeated Characters Given a string S, return the number of substrings of length K with no repeated...
  2. How to use the Leetcode’s Mock Interview Overview to Nail Your Interview? Leetcode has become a de-facto standard for preparing your coding interview. The leetcode has a...
  3. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  4. Bruteforce or Line Sweep Algorithms to Remove Covered Intervals Given a list of intervals, remove all intervals that are covered by another interval in...
  5. The Alien Dictionary Verification Algorithm In an alien language, surprisingly they also use english lowercase letters, but possibly in a...
  6. SQL Coding Exercise – Find Department Highest Salary Submit your solution: https://leetcode.com/problems/department-highest-salary/ As seen, two tables, you are asked to list the highest...
  7. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  8. C++ Coding Exercise – How to Check Duplicates with Sliding Window? Given an array of integers and an integer k, find out whether there are two...

Leave a Reply