Given 2 numbers a and b of same length. The task is to calculate their sum in such a way that when adding two corresponding positions the carry has to be kept with them only instead of propagating to the left.
See the below image for reference:
Examples:
Input: a = 7752 , b = 8834 Output: 151586 Input: a = 123 , b = 456 Output: 579
Approach: First of all, reverse both of the numbers a and b. Now, to generate the resulting sum:
- Extract digits from both a and b.
- Calculate sum of digits.
- If sum of digits is a single digit number, append it directly to the resultant sum.
- Otherwise, reverse the current calculated digit sum and extract digits from it one by one and append to the resultant sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include<bits/stdc++.h>using namespace std;// Function to print sum of 2 numbers// without propagating carryint printSum(int a, int b){ int res = 0; int temp1 = 0, temp2 = 0; // Reverse a while(a) { temp1 = temp1*10 + (a%10); a /= 10; } a = temp1; // Reverse b while(b) { temp2 = temp2*10 + (b%10); b /= 10; } b = temp2; // Generate sum // Since length of both a and b are same, // take any one of them. while(a) { // Extract digits from a and b and add int sum = (a%10 + b%10); // If sum is single digit if(sum/10 == 0) res = res*10 + sum; else { // If sum is not single digit // reverse sum temp1 = 0; while(sum) { temp1 = temp1*10 + (sum%10); sum /= 10; } sum = temp1; // Extract digits from sum and append // to result while(sum) { res = res*10 + (sum%10); sum /=10; } } a/=10; b/=10; } return res;}// Driver codeint main(){ int a = 7752, b = 8834; cout<<printSum(a, b); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function to print sum of 2 numbers // without propagating carry static int printSum(int a, int b) { int res = 0; int temp1 = 0, temp2 = 0; // Reverse a while (a != 0) { temp1 = temp1 * 10 + (a % 10); a /= 10; } a = temp1; // Reverse b while (b != 0) { temp2 = temp2 * 10 + (b % 10); b /= 10; } b = temp2; // Generate sum // Since length of both a and b are same, // take any one of them. while (a != 0) { // Extract digits from a and b and add int sum = (a % 10 + b % 10); // If sum is single digit if (sum / 10 == 0) { res = res * 10 + sum; } else { // If sum is not single digit // reverse sum temp1 = 0; while (sum != 0) { temp1 = temp1 * 10 + (sum % 10); sum /= 10; } sum = temp1; // Extract digits from sum and append // to result while (sum != 0) { res = res * 10 + (sum % 10); sum /= 10; } } a /= 10; b /= 10; } return res; } // Driver code public static void main(String[] args) { int a = 7752, b = 8834; System.out.println(printSum(a, b)); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to print sum of 2 numbers # without propagating carry def printSum(a, b): res, temp1, temp2 = 0, 0, 0 # Reverse a while a > 0: temp1 = temp1 * 10 + (a % 10) a //= 10 a = temp1 # Reverse b while b > 0: temp2 = temp2 * 10 + (b % 10) b //= 10 b = temp2 # Generate sum # Since length of both a and b are same, # take any one of them. while a: # Extract digits from a and b and add Sum = a % 10 + b % 10 # If sum is single digit if Sum // 10 == 0: res = res * 10 + Sum else: # If sum is not single digit # reverse sum temp1 = 0 while Sum > 0: temp1 = temp1 * 10 + (Sum % 10) Sum //= 10 Sum = temp1 # Extract digits from sum and # append to result while Sum > 0: res = res * 10 + (Sum % 10) Sum //= 10 a //= 10 b //= 10 return res # Driver code if __name__ == "__main__": a, b = 7752, 8834 print(printSum(a, b)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of the above approachusing System;class GFG{// Function to print sum of 2 numbers// without propagating carrystatic int printSum(int a, int b){ int res = 0; int temp1 = 0, temp2 = 0; // Reverse a while(a != 0) { temp1 = temp1 * 10 + (a % 10); a /= 10; } a = temp1; // Reverse b while(b != 0) { temp2 = temp2 * 10 + (b % 10); b /= 10; } b = temp2; // Generate sum // Since length of both a and b are same, // take any one of them. while(a != 0) { // Extract digits from a and b and add int sum = (a % 10 + b % 10); // If sum is single digit if(sum / 10 == 0) res = res * 10 + sum; else { // If sum is not single digit // reverse sum temp1 = 0; while(sum != 0) { temp1 = temp1 * 10 + (sum % 10); sum /= 10; } sum = temp1; // Extract digits from sum and append // to result while(sum != 0) { res = res * 10 + (sum % 10); sum /=10; } } a /= 10; b /= 10; } return res;}// Driver codepublic static void Main(){ int a = 7752, b = 8834; Console.Write(printSum(a, b)); }}// This code is contributed // by Akanksha Rai |
PHP
<?php// PHP implementation of the approach// Function to print sum of 2 numbers// without propagating carryfunction printSum($a, $b) { $res = 0; $temp1 = 0; $temp2 = 0; // Reverse a while ($a != 0) { $temp1 = $temp1 * 10 + ($a % 10); $a = (int)($a / 10); } $a = $temp1; // Reverse b while ($b != 0) { $temp2 = $temp2 * 10 + ($b % 10); $b = (int)($b / 10); } $b = $temp2; // Generate sum // Since length of both a and b are same, // take any one of them. while ($a != 0) { // Extract digits from a and b and add $sum = ($a % 10 + $b % 10); // If sum is single digit if ((int)($sum / 10) == 0) { $res = $res * 10 + $sum; } else { // If sum is not single digit // reverse sum $temp1 = 0; while ($sum != 0) { $temp1 = $temp1 * 10 + ($sum % 10); $sum = (int)($sum / 10); } $sum = $temp1; // Extract digits from sum and append // to result while ($sum != 0) { $res = $res * 10 + ($sum % 10); $sum = (int)($sum / 10); } } $a = (int)($a / 10); $b = (int)($b / 10); } return $res;}// Driver code$a = 7752; $b = 8834;echo(printSum($a, $b));// This code contributed by Code_Mech.?> |
Javascript
<script> // Javascript implementation of the above approach // Function to print sum of 2 numbers // without propagating carry function printSum(a, b) { var res = 0; var temp1 = 0, temp2 = 0; // Reverse a while (a) { temp1 = temp1 * 10 + (a % 10); a = parseInt(a / 10); } a = temp1; // Reverse b while (b) { temp2 = temp2 * 10 + (b % 10); b = parseInt(b / 10); } b = temp2; // Generate sum // Since length of both a and b are same, // take any one of them. while (a) { // Extract digits from a and b and add var sum = (a % 10 + b % 10); // If sum is single digit if (parseInt(sum / 10) == 0) res = res * 10 + sum; else { // If sum is not single digit // reverse sum temp1 = 0; while (sum) { temp1 = temp1 * 10 + (sum % 10); sum = parseInt(sum / 10); } sum = temp1; // Extract digits from sum and append // to result while (sum) { res = res * 10 + (sum % 10); sum = parseInt(sum / 10); } } a = parseInt(a / 10); b = parseInt(b / 10); } return res; } // Driver code var a = 7752, b = 8834; document.write(printSum(a, b));// This code is contributed by rrrtnx. </script> |
Output:
151586
Time Complexity: O(logN), as we are doing a floor division of N with 10 while it is greater than 0.
Auxiliary Space: O(1), as we are not using any extra space.
Another Approach
Algorithm
Let we have two numbers
a = 48368
b = 3224
Step 1: First, we will split number both the number into the digits and will store into the array as given below : –
arr1 = [4, 8, 3, 6, 8]
arr2 = [3, 2, 2, 4]
Step 2: After splitting and storing we will make the length of both array equal to each other by adding the 0 in their beginning whose length is less than the other array sothat the addition can be performed easily as explained below : –
As we can that arr2 length is less as compared to arr1. So,
arr2 = [0, 3, 2, 2, 4]
Step 3: Now, we will add every digit of the array either from the last index or start index(as per your choice) and will store sum into the another array as explained below : –
we are adding the digits are from starting index and will push into the array.
arr1 = [4, 8, 3, 6, 8]
arr2 = [0, 3, 2, 2, 4]
digitSum = [4, 11, 5, 8, 12]
Step 4: Finally we have to join the numbers of digitSum array from the start index upto end index as explained below : –
Ans = 4115812
Step 5: Print the final answer.
Implementation of the Above approach as given below : –
C++
#include<bits/stdc++.h>using namespace std;// Logic for storing the digits into the arrayvoid getDigits(vector<int> &v, int a){ while(a != 0){ v.push_back(a%10); a /= 10; } reverse(v.begin(), v.end());}// logic for inserting the 0 at the beginningvoid insertDataAtBegin(vector<int> &v, int size){ for(int i = 0; i < size; i++){ v.insert(v.begin(), 0); }}// logic for the addition of the digits and storing// into the new arrayvector<int> SumDigits(vector<int> vec1, vector<int> vec2){ vector<int> result; for(int i = 0; i < vec1.size(); i++){ result.push_back(vec1[i]+vec2[i]); } return result;}// logic for joining for the numbers of the arrayvoid convertIntoNumber(vector<int> result, long long &num){ string ans; for(int i = 0; i < result.size(); i++){ if(result[i] < 10){ ans.push_back(char(result[i]+48)); } else{ ans.push_back(char((result[i]/10)+48)); ans.push_back(char((result[i]%10)+48)); } } num = stoi(ans);}int main() { int a = 48368; int b = 3224; vector<int> storeA; vector<int> storeB; // storing the digits of both number into // the vector getDigits(storeA, a); getDigits(storeB, b); // Making the size of both vector equal // sothat we can add the digits easily if(storeA.size() > storeB.size()){ insertDataAtBegin(storeB, storeA.size()-storeB.size()); } if(storeB.size() > storeA.size()){ insertDataAtBegin(storeA, storeB.size()-storeA.size()); } vector<int> result = SumDigits(storeA, storeB); long long finalAns = 0; convertIntoNumber(result, finalAns); cout << finalAns; cout << endl; return 0;} |
Java
// Java Code for the above approachimport java.io.*;import java.util.*;class GFG { // Logic for storing the digits into the array static void getDigits(ArrayList<Integer> v, int a) { while (a != 0) { v.add(a % 10); a /= 10; } Collections.reverse(v); } // logic for inserting the 0 at the beginning static void insertDataAtBegin(ArrayList<Integer> v, int size) { for (int i = 0; i < size; i++) { v.add(0, 0); } } // logic for the addition of the digits and storing into // the new array static ArrayList<Integer> SumDigits(ArrayList<Integer> vec1, ArrayList<Integer> vec2) { ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i < vec1.size(); i++) { result.add(vec1.get(i) + vec2.get(i)); } return result; } // logic for joining for the numbers of the array static void convertIntoNumber(ArrayList<Integer> result, long[] num) { StringBuilder ans = new StringBuilder(); for (int i = 0; i < result.size(); i++) { if (result.get(i) < 10) { ans.append( Character.forDigit(result.get(i), 10)); } else { ans.append(Character.forDigit( result.get(i) / 10, 10)); ans.append(Character.forDigit( result.get(i) % 10, 10)); } } num[0] = Long.parseLong(ans.toString()); } public static void main(String[] args) { int a = 48368; int b = 3224; ArrayList<Integer> storeA = new ArrayList<>(); ArrayList<Integer> storeB = new ArrayList<>(); // storing the digits of both number into the vector getDigits(storeA, a); getDigits(storeB, b); // Making the size of both vector equal so that we // can add the digits easily if (storeA.size() > storeB.size()) { insertDataAtBegin(storeB, storeA.size() - storeB.size()); } if (storeB.size() > storeA.size()) { insertDataAtBegin(storeA, storeB.size() - storeA.size()); } ArrayList<Integer> result = SumDigits(storeA, storeB); long[] finalAns = { 0 }; convertIntoNumber(result, finalAns); System.out.println(finalAns[0]); }}// This code is contributed by karthik. |
Python3
# logic for storing the digits into the arraydef getDigits(a): data = [] while a != 0: data.append(a%10) a //= 10 data.reverse() return data# logic for inserting the 0 at beginningdef insertDataAtBegin(v, size): for i in range(size): v = [0] + v return v# Logic for the addition of the digits and storing# into the new arraydef sumDigits(vec1, vec2): result = [] for i in range(len(vec1)): result.append(vec1[i]+vec2[i]) return result# Logic for joining the number of the arraydef convertIntoNumber(result): ans = [] for i in range(len(result)): if result[i] < 10: ans.append(chr(result[i]+48)) else: ans.append(chr((result[i]//10)+48)) ans.append(chr((result[i]%10)+48)) num = "".join(ans) num = int(num) return numa = 48368b = 3224# Storing the digits of both number into# vectorstoreA = getDigits(a)storeB = getDigits(b)# Making the size of both vector equal# sothat we can add the the digits easilyif len(storeA) > len(storeB): storeB = insertDataAtBegin(storeB, len(storeA)-len(storeB))if len(storeB) > len(storeA): storeA = insertDataAtBegin(storeA, len(storeB)-len(storeA))result = sumDigits(storeA, storeB)final_ans = convertIntoNumber(result)print(final_ans) |
C#
// C# Code for the above approachusing System;using System.Collections.Generic;public class GFG { // Logic for storing the digits into the array static void GetDigits(List<int> v, int a) { while (a != 0) { v.Add(a % 10); a /= 10; } v.Reverse(); } // logic for inserting the 0 at the beginning static void InsertDataAtBegin(List<int> v, int size) { for (int i = 0; i < size; i++) { v.Insert(0, 0); } } // logic for the addition of the digits and storing into // the new array static List<int> SumDigits(List<int> vec1, List<int> vec2) { List<int> result = new List<int>(); for (int i = 0; i < vec1.Count; i++) { result.Add(vec1[i] + vec2[i]); } return result; } // logic for joining for the numbers of the array static void ConvertIntoNumber(List<int> result, ref long num) { string ans = ""; for (int i = 0; i < result.Count; i++) { if (result[i] < 10) { ans += result[i].ToString(); } else { ans += (result[i] / 10).ToString(); ans += (result[i] % 10).ToString(); } } num = long.Parse(ans); } static public void Main() { // Code int a = 48368; int b = 3224; List<int> storeA = new List<int>(); List<int> storeB = new List<int>(); // storing the digits of both number into the vector GetDigits(storeA, a); GetDigits(storeB, b); // Making the size of both vector equal so that we // can add the digits easily if (storeA.Count > storeB.Count) { InsertDataAtBegin(storeB, storeA.Count - storeB.Count); } if (storeB.Count > storeA.Count) { InsertDataAtBegin(storeA, storeB.Count - storeA.Count); } List<int> result = SumDigits(storeA, storeB); long finalAns = 0; ConvertIntoNumber(result, ref finalAns); Console.WriteLine(finalAns); }}// This code is contributed by lokesh. |
Javascript
function getDigits(v, a) { // Logic for storing the digits into the array while (a != 0) { v.push(a % 10); a = Math.floor(a / 10); } v.reverse();}function insertDataAtBegin(v, size) { // logic for inserting the 0 at the beginning for (let i = 0; i < size; i++) { v.unshift(0); }}function sumDigits(vec1, vec2) { // logic for the addition of the digits and storing // into the new array let result = []; for (let i = 0; i < vec1.length; i++) { result.push(vec1[i] + vec2[i]); } return result;}function convertIntoNumber(result) { // logic for joining for the numbers of the array let ans = ""; for (let i = 0; i < result.length; i++) { if (result[i] < 10) { ans += String(result[i]); } else { ans += String(Math.floor(result[i] / 10)); ans += String(result[i] % 10); } } return parseInt(ans);}let a = 48368;let b = 3224;let storeA = [];let storeB = [];// storing the digits of both number into// the vectorgetDigits(storeA, a);getDigits(storeB, b);// Making the size of both vector equal// sothat we can add the digits easilyif (storeA.length > storeB.length) { insertDataAtBegin(storeB, storeA.length - storeB.length);}if (storeB.length > storeA.length) { insertDataAtBegin(storeA, storeB.length - storeA.length);}let result = sumDigits(storeA, storeB);let finalAns = convertIntoNumber(result);console.log(finalAns);// This code is contributed by ratiagarawal. |
Output
4115812
Time Complexity: O(logN), where N = number
Auxiliary Space: O(logN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
