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: 22320931522333Input: 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 stringsstring 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 numberstring 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 stringsstring 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 Codeint 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 strsingsdef 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 numberdef 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 strsingsdef 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 Codestrs1 = "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 complementusing 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 stringsfunction 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 numberfunction 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 stringsfunction 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 Codelet 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 complementimport 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:
1
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
