Subtraction of two large numbers using 10’s complement

0 0 10 minutes read

Given two strings str1 and str2 of given lengths N and M respectively, each representing a large number, the task is to subtract one from the other using 10’s complement.

Example:

Input: N = 10, str1 = “3434243434”, M = 14, str2 = “22324365765767”
Output: 22320931522333

Input: N = 20, str1 = “12345334233242431433”, M = 20, str2 = “12345334233242431432”
Output: 1

Approach: The basic idea is similar to Subtraction of two numbers using 2’s complement.

Subtraction of given strings can be written as
Str1 – Str2 = Str1 + (- Str2) = Str1 + (10’s complement of Str2)

Follow the steps below to solve the problem:

Compare the lengths of the two strings and store the smaller of the two in str2.
Calculate 10’s complement of str2.
Now, add 10’s complement of str2 to str1.
If any carry is generated, then drop the carry.
If no carry is generated, then the complement of str1 is the final answer.

Below is the implementation of the above approach:

C++

// C++ Program to calculate the
// subtraction of two large number
// using 10's complement
#include <bits/stdc++.h>
using namespace std;
 
// Function to return sum of two
// large numbers given as strings
string sumBig(string a, string b)
{
 
    // Compare their lengths
    if (a.length() > b.length())
        swap(a, b);
 
    // Stores the result
    string str = "";
 
    // Store the respective lengths
    int n1 = a.length(), n2 = b.length();
 
    int diff = n2 - n1;
 
    // Initialize carry
    int carry = 0;
 
    // Traverse from end of both strings
    for (int i = n1 - 1; i >= 0; i--) {
 
        // Compute sum of
        // current digits and carry
        int sum
            = ((a[i] - '0')
               + (b[i + diff] - '0') + carry);
 
        // Store the result
        str.push_back(sum % 10 + '0');
 
        // Update carry
        carry = sum / 10;
    }
 
    // Add remaining digits of str2[]
    for (int i = n2 - n1 - 1; i >= 0; i--) {
 
        int sum = ((b[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;
}
 
// Function return 10's
// complement of given number
string complement10(string v)
{
    // Stores the complement
    string complement = "";
 
    // Calculate 9's complement
    for (int i = 0; i < v.size(); i++) {
 
        // Subtract every bit from 9
        complement += '9' - v[i] + '0';
    }
 
    // Add 1 to 9's complement
    // to find 10's complement
    complement = sumBig(complement, "1");
    return complement;
}
 
// Function returns subtraction
// of two given numbers as strings
string subtract(string a, string b)
{
 
    // If second string is larger
    if (a.length() < b.length())
        swap(a, b);
 
    // Calculate respective lengths
    int l1 = a.length(), l2 = b.length();
 
    // If lengths aren't equal
    int diffLen = l1 - l2;
 
    for (int i = 0; i < diffLen; i++) {
 
        // Insert 0's to the beginning
        // of b to make both the lengths equal
        b = "0" + b;
    }
 
    // Add (complement of B) and A
    string c = sumBig(a, complement10(b));
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.length() > a.length()) {
        string::iterator it;
 
        // Erase first bit
        it = c.begin();
 
        c.erase(it);
 
        // Trim zeros at the beginning
        it = c.begin();
 
        while (*it == '0')
            c.erase(it);
 
        return c;
    }
 
    // If both lengths are equal
    else {
        return complement10(c);
    }
}
 
// Driver Code
int main()
{
 
    string str1 = "12345334233242431433";
    string str2 = "12345334233242431432";
 
    cout << subtract(str1, str2) << endl;
 
    return 0;
}

Python3

# Python3 Program to calculate the
# subtraction of two large number
# using 10's complement
 
# Function to return sums of two
# large numbers given as strsings
def sumsBig(a, b):
 
    # Compare their lengths
    if (len(a) > len(b)):
     
        temp = a;
        a = b;
        b = temp;
     
    # Stores the result
    strs = "";
 
    # Store the respective lengths
    n1 = len(a) 
    n2 = len(b);
 
    diff = n2 - n1;
 
    # Initialize carry
    carry = 0;
 
    # Traverse from end of both strsings
    for i in range(n1 - 1, -1, -1):
 
        # Compute sums of
        # current digits and carry
        sums = (int(a[i]) + int(b[i + diff]) + carry);
 
        # Store the result
        strs += str(sums % 10);
 
        # Update carry
        carry = int(sums / 10);
     
    # Add remaining digits of strs2[]
    for i in range(n2 - n1 - 1, -1, -1):
 
        sums = ( int(b[i]) + carry);
 
        strs += str(sums % 10);
        carry = int(sums / 10);
     
    # Add remaining carry
    if (carry > 0):
        strs += str(carry);
 
    # Reverse resultant strsing
    strs = strs[::-1]
 
    return strs;
 
# Function return 10's
# complement of given number
def complement10(v):
 
    # Stores the complement
    complement = "";
 
    # Calculate 9's complement
    for i in range(len(v)):
 
        # Subtract every bit from 9
        complement +=   str(9 - int(v[i]));
     
    # Add 1 to 9's complement
    # to find 10's complement
    complement = sumsBig(complement, "1");
    return complement;
 
# Function returns subtraction
# of two given numbers as strsings
def subtract(a, b):
 
    # If second strsing is larger
    if (len(a) < len(b)):    
        temp = b;
        b = a ;
        a = temp;
     
    # Calculate respective lengths
    l1 = len(a) 
    l2 = len(b);
 
    # If lengths aren't equal
    diffLen = l1 - l2;
     
    for i in range(diffLen):
 
        # Insert 0's to the beginning
        # of b to make both the lengths equal
        b = "0" + b;
     
    # Add (complement of B) and A
    c = sumsBig(a, complement10(b));
 
    # If length of new strsing is greater
    # than length of first strsing,
    # than carry is generated
    if (len(c) > len(a)): 
 
        # Erase first bit
        c = c[1::];
        # Trim zeros at the beginning
        while (c[0] == '0'):
            c = c[1::]
 
        return c;
     
    # If both lengths are equal
    else :
        return complement10(c);
     
# Driver Code
strs1 = "12345334233242431433";
strs2 = "12345334233242431432";
 
print(subtract(strs1, strs2));
 
# This code is contributed by phasing17.

C#

// C# Program to calculate the
// subtraction of two large number
// using 10's complement
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
   
  // Function to return sum of two
  // large numbers given as strings
  static string sumBig(string a, string b)
  {
 
    // Compare their lengths
    if (a.Length > b.Length)
    {
      string temp = b;
      b = a;
      a = temp;
    }
 
    // Stores the result
    string str = "";
 
    // Store the respective lengths
    int n1 = a.Length, n2 = b.Length;
 
    int diff = n2 - n1;
 
    // Initialize carry
    int carry = 0;
 
    // Traverse from end of both strings
    for (int i = n1 - 1; i >= 0; i--) {
 
      // Compute sum of
      // current digits and carry
      int sum
        = ((a[i] - '0')
           + (b[i + diff] - '0') + carry);
 
      // Store the result
      str += (char)(sum % 10 + '0');
 
      // Update carry
      carry = sum / 10;
    }
 
    // Add remaining digits of str2[]
    for (int i = n2 - n1 - 1; i >= 0; i--) {
 
      int sum = ((b[i] - '0') + carry);
 
      str += (char)(sum % 10 + '0');
      carry = sum / 10;
    }
 
    // Add remaining carry
    if (carry != 0)
      str += (char)(carry + '0');
 
    // Reverse resultant string
    char[] strs = str.ToCharArray();
    Array.Reverse(strs);
 
    return new string(strs);
  }
 
  // Function return 10's
  // complement of given number
  static string complement10(string v)
  {
    // Stores the complement
    string complement = "";
 
    // Calculate 9's complement
    for (int i = 0; i < v.Length; i++) {
 
      // Subtract every bit from 9
      complement += (char)('9' - v[i] + '0');
    }
 
    // Add 1 to 9's complement
    // to find 10's complement
    complement = sumBig(complement, "1");
    return complement;
  }
 
  // Function returns subtraction
  // of two given numbers as strings
  static string subtract(string a, string b)
  {
 
    // If second string is larger
    if (a.Length < b.Length)
    {
      var t = b;
      b = a;
      a = t;
    }
 
    // Calculate respective lengths
    int l1 = a.Length, l2 = b.Length;
 
    // If lengths aren't equal
    int diffLen = l1 - l2;
 
    for (int i = 0; i < diffLen; i++) {
 
      // Insert 0's to the beginning
      // of b to make both the lengths equal
      b = "0" + b;
    }
 
    // Add (complement of B) and A
    string c = sumBig(a, complement10(b));
 
 
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.Length > a.Length) {
 
      var c1 = c.ToCharArray().ToList();
 
      // Erase first bit
      c1.RemoveAt(0);
 
      // Trim zeros at the beginning
      while(c1[0] == '0')
        c1.RemoveAt(0);
 
      return new string(c1.ToArray());
 
    }
 
    // If both lengths are equal
    else {
      return complement10(c);
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    string str1 = "12345334233242431433";
    string str2 = "12345334233242431432";
 
    Console.WriteLine(subtract(str1, str2));
  }
}
 
// This code is contributed by phasing17.

Javascript

// JS Program to calculate the
// subtraction of two large number
// using 10's complement
 
// Function to return sum of two
// large numbers given as strings
function sumBig(a, b)
{
 
    // Compare their lengths
    if (a.length > b.length)
    {
        let temp = a;
        a = b;
        b = temp;
    }
 
    // Stores the result
    let str = "";
 
    // Store the respective lengths
    let n1 = a.length, n2 = b.length;
 
    let diff = n2 - n1;
 
    // Initialize carry
    let carry = 0;
 
    // Traverse from end of both strings
    for (let i = n1 - 1; i >= 0; i--) {
 
        // Compute sum of
        // current digits and carry
        let sum
            = (parseInt(a[i])
               + parseInt(b[i + diff]) + carry);
 
        // Store the result
        str += (sum % 10).toString();
 
        // Update carry
        carry = Math.floor(sum / 10);
    }
 
    // Add remaining digits of str2[]
    for (let i = n2 - n1 - 1; i >= 0; i--) {
 
        let sum = ( parseInt(b[i]) + carry);
 
        str += (sum % 10).toString();
        carry = Math.floor(sum / 10);
    }
 
    // Add remaining carry
    if (carry > 0)
        str += (carry).toString();
 
    // Reverse resultant string
    str = str.split("").reverse().join("")
 
    return str;
}
 
// Function return 10's
// complement of given number
function complement10(v)
{
    // Stores the complement
    let complement = "";
 
    // Calculate 9's complement
    for (var i = 0; i < v.length; i++) {
 
        // Subtract every bit from 9
        complement +=   (9 - parseInt(v[i])).toString();
    }
 
    // Add 1 to 9's complement
    // to find 10's complement
    complement = sumBig(complement, "1");
    return complement;
}
 
// Function returns subtraction
// of two given numbers as strings
function subtract(a, b)
{
 
    // If second string is larger
    if (a.length < b.length)
    {
        let temp = b;
        b = a ;
        a = temp;
    }
 
    // Calculate respective lengths
    let l1 = a.length, l2 = b.length;
 
    // If lengths aren't equal
    let diffLen = l1 - l2;
 
    for (let i = 0; i < diffLen; i++) {
 
        // Insert 0's to the beginning
        // of b to make both the lengths equal
        b = "0" + b;
    }
 
    // Add (complement of B) and A
    let c = sumBig(a, complement10(b));
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.length > a.length) {
 
        // Erase first bit
       c = c.substr(1);
 
 
        // Trim zeros at the beginning
         
 
        while (c[0] == '0')
            c = c.substr(1)
 
        return c;
    }
 
    // If both lengths are equal
    else {
        return complement10(c);
    }
}
 
// Driver Code
let str1 = "12345334233242431433";
let str2 = "12345334233242431432";
 
console.log(subtract(str1, str2));
 
// This code is contributed by phasing17.

Java

// Java Program to calculate the
// subtraction of two large number
// using 10's complement
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class Main {
    // Function to return sum of two large numbers given as
    // strings
    public static String sumBig(String a, String b)
    {
        // Compare their lengths
        if (a.length() > b.length()) {
            String c = a;
            a = b;
            b = c;
        }
 
        // Stores the result
        String str = "";
 
        // Store the respective lengths
        int n1 = a.length(), n2 = b.length();
        int diff = n2 - n1;
 
        // Initialize carry
        int carry = 0;
 
        // Traverse from end of both strings
        for (int i = n1 - 1; i >= 0; i--) {
            // Compute sum of current digits and carry
            int sum
                = ((a.charAt(i) - '0')
                   + (b.charAt(i + diff) - '0') + carry);
 
            // Store the result
            str += (char)(sum % 10 + '0');
 
            // Update carry
            carry = sum / 10;
        }
 
        // Add remaining digits of b
        for (int i = n2 - n1 - 1; i >= 0; i--) {
            int sum = ((b.charAt(i) - '0') + carry);
 
            str += (char)(sum % 10 + '0');
            carry = sum / 10;
        }
 
        // Add remaining carry
        if (carry > 0)
            str += (char)(carry + '0');
 
        // Reverse resultant string
        StringBuilder sb = new StringBuilder(str);
        sb.reverse();
        return sb.toString();
    }
 
    // Function to return 10's complement of given number
    public static String complement10(String v)
    {
        // Stores the complement
        String complement = "";
 
        // Calculate 9's complement
        for (int i = 0; i < v.length(); i++) {
            // Subtract every bit from 9
            complement += (char)('9' - v.charAt(i) + '0');
        }
 
        // Add 1 to 9's complement to find 10's complement
        complement = sumBig(complement, "1");
        return complement;
    }
 
    // Function to return subtraction of two given numbers
    // as strings
    public static String subtract(String a, String b)
    {
        // If second string is larger
        if (a.length() < b.length()) {
            String c = a;
            a = b;
            b = c;
        }
 
        // Calculate respective lengths
        int l1 = a.length(), l2 = b.length();
 
        // If lengths aren't equal
        int diffLen = l1 - l2;
 
        for (int i = 0; i < diffLen; i++) {
            // Insert 0's to the beginning of b to make both
            // the lengths equal
            b = "0" + b;
        }
 
        // Add (complement of B) and A
        String c = sumBig(a, complement10(b));
 
        // If length of new string is greater than length of
        // first string, then carry is generated
        if (c.length() > a.length()) {
            // Erase first bit
            c = c.substring(1);
 
            // Trim zeros at the beginning
            while (c.charAt(0) == '0')
                c = c.substring(1);
 
            return c;
        }
        else {
            // If both lengths are equal
            return complement10(c);
        }
    }
 
    // Driver's Code
    public static void main(String[] args)
    {
 
        String str1 = "12345334233242431433";
        String str2 = "12345334233242431432";
        System.out.println(subtract(str1, str2));
    }
}

Output:

Time Complexity: O(max(N, M))
Auxiliary Space: O(max(N, M))

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!