Subtraction of two large numbers using 9’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 9’s complement.
Examples:

Input: N = 17, str1 = “12345678987654321”, M = 11, str2 = “22324324343”
Output: 12345656663329978
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 + (9’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 9’s complement of str2.
Now, add 9’s complement of str2 to str1.
If any carry is generated, insert at the beginning of str1.
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 implement
// the above approach
#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 9's
// complement of given number
string complement9(string v)
{
    // Stores the complement
    string complement = "";
 
    for (int i = 0; i < v.size(); i++) {
 
        // Subtract every bit from 9
        complement += '9' - v[i] + '0';
    }
 
    // Return the result
    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 are 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, complement9(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;
 
        // bit1 is the carry bit
        char bit1 = c[0];
        string bit = { bit1 };
        it = c.begin();
        c.erase(it);
        c = sumBig(c, bit);
        return c;
    }
 
    // If both lengths are equal
    else {
        return complement9(c);
    }
}
 
// Driver Code
int main()
{
 
    string str1 = "12345678987654321";
    string str2 = "22324324343";
 
    cout << subtract(str1, str2) << endl;
 
    return 0;
}

Java

import java.io.*;
import java.lang.*;
import java.util.*;
public class Main
{
 
  // 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 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 str2[]
    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
    String rev = "";
 
    for (int i = str.length() - 1; i >= 0; i--)
      rev = rev + str.charAt(i);
 
    return rev;
  }
  // Function return 9's
  // complement of given number
  static String complement9(String v)
  {
    // Stores the complement
    String complement = "";
 
    for (int i = 0; i < v.length(); i++) {
 
      // Subtract every bit from 9
      int x = '9' - v.charAt(i) + '0';
      complement += (char)x;
    }
    // Return the result
    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()) {
      String c = a;
      a = b;
      b = c;
    }
 
    // Calculate respective lengths
    int l1 = a.length(), l2 = b.length();
 
    // If lengths are 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, complement9(b));
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.length() > a.length()) {
 
      // bit1 is the carry bit
      char bit1 = c.charAt(0);
      String bit = "";
      bit += bit1;
      StringBuilder sb = new StringBuilder(c);
      sb.deleteCharAt(0);
      c = sb.toString();
      c = sumBig(c, bit);
      return c;
    }
 
    // If both lengths are equal
    else {
      return complement9(c);
    }
  }
  public static void main(String[] args)
  {
    String str1 = "12345678987654321";
    String str2 = "22324324343";
 
    System.out.println(subtract(str1, str2));
  }
}
 
// This code is contributed by garg28harsh.

Python3

# Python3 Program to implement
# the above approach
 
# Function to return sum of two
# large numbers given as strings
def sumBig(a, b):
 
    # Compare their lengths
    if (len(a) > len(b)):
     
        temp = a;
        a = b;
        b = temp;
     
     
    # Stores the result
    str1 = "";
 
    # Store the respective lengths
    n1 = len(a)
    n2 = len(b);
 
    diff = n2 - n1;
 
    # Initialize carry
    carry = 0;
 
    # Traverse from end of both strings
    for i in range(n1 - 1, -1, -1):
        # Compute sum of
        # current digits and carry
        sums = ( int(a[i]) + int(b[i + diff]) + carry);
 
        # Store the result
        str1 += str((sums % 10));
 
        # Update carry
        carry = int(sums / 10);
     
 
    # Add remaining digits of str2[]
    for i in range(n2 - n1 - 1, -1, -1):
 
        sums = (int(b[i]) + carry);
 
        str1 += str((sums % 10));
        carry = int(sums/ 10);
     
    # Add remaining carry
    if (carry > 0):
        str1 += str(carry)
 
    # Reverse resultant string
    str1 = str1[::-1]
 
    return str1;
 
# Function return 9's
# complement of given number
def complement9( v):
 
    # Stores the complement
    complement = "";
     
    for i in range(len(v)):
 
        # Subtract every bit from 9
        complement += str(9 - int(v[i]));
     
    # Return the result
    return complement;
 
# Function returns subtraction
# of two given numbers as strings
def subtract(a, b):
 
    # If second string is larger
    if (len(a) < len(b)):
     
        temp = a;
        a = b;
        b = temp;
     
    # Calculate respective lengths
    l1 = len(a)
    l2 = len(b);
 
    # If lengths are 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 = sumBig(a, complement9(b));
 
    # If length of new string is greater
    # than length of first string,
    # than carry is generated
    if (len(c) > len(a)): 
 
        # bit1 is the carry bit
        bit1 = c[0];
        bit = [ bit1 ];
        c = c[1::];
        c = sumBig(c, bit);
        return c;
     
    # If both lengths are equal
    else :
        return complement9(c);
     
# Driver Code
str1 = "12345678987654321";
str2 = "22324324343";
 
print(subtract(str1, str2));
 
# This code is contributed by phasing17.

C#

// C# Program to implement
// the above approach
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)
    {var 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[] strc = str.ToCharArray();
    Array.Reverse(strc);
    return new string(strc);
  }
 
  // Function return 9's
  // complement of given number
  static string complement9(string v)
  {
    // Stores the complement
    string complement = "";
 
    for (int i = 0; i < v.Length; i++) {
 
      // Subtract every bit from 9
      complement += (char)('9' - v[i] + '0');
    }
 
    // Return the result
    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 temp = b; b = a; a = temp; };
 
    // Calculate respective lengths
    int l1 = a.Length,
    l2 = b.Length;
 
    // If lengths are 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, complement9(b));
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.Length > a.Length) {
      List<char> c1 = c.ToList();
 
 
      // bit1 is the carry bit
      char bit1 = c[0];
      string bit = "" + bit1;
 
      c1.RemoveAt(0);
      c = new string(c1.ToArray());
 
      c = sumBig(c, bit);
      return c;
    }
 
    // If both lengths are equal
    else {
      return complement9(c);
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    string str1 = "12345678987654321";
    string str2 = "22324324343";
 
    Console.WriteLine(subtract(str1, str2));
  }
}
 
// This code is contributed by phasing17.

Javascript

// JS Program to implement
// the above approach
 
// 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 (var i = n2 - n1 - 1; i >= 0; i--) {
 
        var 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 9's
// complement of given number
function complement9( v)
{
    // Stores the complement
    let complement = "";
 
    for (var i = 0; i < v.length; i++) {
 
        // Subtract every bit from 9
        complement += (9 - parseInt(v[i])).toString();
    }
 
    // Return the result
    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 = a;
        a = b;
        b = temp;
    }
 
    // Calculate respective lengths
    let l1 = a.length,
        l2 = b.length;
 
    // If lengths are 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, complement9(b));
 
    // If length of new string is greater
    // than length of first string,
    // than carry is generated
    if (c.length > a.length) {
 
        // bit1 is the carry bit
        let bit1 = c[0];
        let bit = [ bit1 ];
        c = c.substr(1);
        c = sumBig(c, bit);
        return c;
    }
 
    // If both lengths are equal
    else {
        return complement9(c);
    }
}
 
// Driver Code
let str1 = "12345678987654321";
let str2 = "22324324343";
 
console.log(subtract(str1, str2));
 
// This code is contributed by phasing17.

Output:

12345656663329978

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!