Addition of two numbers without propagating Carry

0 0 12 minutes read

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 carry
int 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 code
int main()
{
    int a = 7752, b = 8834;
    cout<<printSum(a, b);
     
    return 0;
}

Java

// Java implementation of the approach
class 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 approach
using System;
 
class 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()
{
    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 carry
function 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:

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 array
void 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 beginning
void 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 array
vector<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 array
void 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 approach
import 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 array
def getDigits(a):
    data = []
    while a != 0:
        data.append(a%10)
        a //= 10
    data.reverse()
    return data
 
# logic for inserting the 0 at beginning
def 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 array
def 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 array
def 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 num
 
 
a = 48368
b = 3224
 
 
# Storing the digits of both number into
# vector
storeA = getDigits(a)
storeB = getDigits(b)
 
# Making the size of both vector equal
# sothat we can add the the digits easily
if 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 approach
 
using 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 vector
getDigits(storeA, a);
getDigits(storeB, b);
 
// Making the size of both vector equal
// sothat we can add the digits easily
if (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

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 zambiatek!