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