Question

Write a function to add two large integers of any length, say up to 200 digits. A suggested approach is as follows: treat each number as a list(array), each of whose elements is a block of digits of that number (say block of 1 to 4 digits, your choice). For example the integer 123456789101112 might be stored with N(1)

Answer 1

see explaination

Step-by-step explanation:

/ C++ program to find sum and product of two large numbers.

#include<bits/stdc++.h>

#include<cstring>

using namespace std;

// Multiplies str1 and str2

string big_multiply(string num1, string num2)

{

int n1 = num1.size();

int n2 = num2.size();

if (n1 == 0 || n2 == 0)

return "0";

// will keep the result number in vector

// in reverse order

vector<int> result(n1 + n2, 0);

int i_n1 = 0;

int i_n2 = 0;

// Go from right to left in num1

for (int i=n1-1; i>=0; i--)

{

int carry = 0;

int n1 = num1[i] - '0';

// To shift position to left after every

// multiplication of a digit in num2

i_n2 = 0;

// Go from right to left in num2

for (int j=n2-1; j>=0; j--)

{

// Take current digit of second number

int n2 = num2[j] - '0';

int sum = n1*n2 + result[i_n1 + i_n2] + carry;

carry = sum/10;

// Store result

result[i_n1 + i_n2] = sum % 10;

i_n2++;

}

// store carry in next cell

if (carry > 0)

result[i_n1 + i_n2] += carry;

i_n1++;

}

// ignore '0's from the right

int i = result.size() - 1;

while (i>=0 && result[i] == 0)

i--;

if (i == -1)

return "0";

// generate the result string

string s = "";

while (i >= 0)

s += std::to_string(result[i--]);

return s;

}

// Function for finding sum of larger numbers

string findSum(string str1, string str2)

{

if (str1.length() > str2.length())

swap(str1, str2);

// Take an empty string for storing result

string str = "";

// Calculate lenght of both string

int n1 = str1.length(), n2 = str2.length();

int diff = n2 - n1;

// Initialy take carry zero

int carry = 0;

// Traverse from end of both strings

for (int i=n1-1; i>=0; i--)

{

int sum = ((str1[i]-'0') +

(str2[i+diff]-'0') +

carry);

str.push_back(sum%10 + '0');

carry = sum/10;

}

// Add remaining digits of str2[]

for (int i=n2-n1-1; i>=0; i--)

{

int sum = ((str2[i]-'0')+carry);

str.push_back(sum%10 + '0');

carry = sum/10;

}

// Add remaining carry

if (carry)

str.push_back(carry+'0');

// reverse resultant string

reverse(str.begin(), str.end());

return str;

}

// Driver function code

int main()

{

string big_str1 = "1235421415454545454545454544";

string big_str2 = "1714546546546545454544548544544545";

cout <<"Sum of two number: "<< findSum(big_str1, big_str2)<<endl;

cout <<"Mutiplication of two number: "<< big_multiply(big_str1, big_str2);

return 0;

}