Summation of Alphanumeric Strings
Just like our number system where we have 10 digits starting from 0 to 9, Geek has created a custom numerical system where he has 36 digits which are 0 to 9 then A to Z where ‘0‘ is the smallest, and ‘Z‘ is the largest number, which follows their respective order (Similar to Hexadecimal number system till F). Your task is to calculate the sum of the numeric values represented by two strings (geek numbers) within this unique numbering system.
Real number system: 0<1<2< ….. 7<8<9. and 9+1=10.
Geek number system: 0<1<2< ….. 7<8<9<A<B<C ….. X<Y<Z,
In the decimal number system, we use 1 digit combination from 0 to 9 but after that the single-digit combination ends, that’s why we use 2 digits starting from 10 which is the smallest 2-digit combination (’00’ equals ‘0’ that’s why we cannot use it). Similarly, in the geek number system we use single-digit combinations from 0 to 9 then A to Z but after Z, the single-digit combination ends, that’s why we use 2 digit combination starting from 10 which is the smallest 2-digit combination (’00’ equals ‘0’ that’s why we cannot use it).
Note: Just like our mathematical addition we will always start addition from the rightmost side, moving to the leftmost side of the strings (geek number).
Examples:
Input: str1 = 0ZZ, str2 = 321
Output: 420
Explanation: Starting from the leftmost of both the strings which are Z (0ZZ) and 1 (321) which will add to give 10 and where we will take 0 in answer and 1 as carry, Then 2nd rightmost digit of both strings which is Z (0ZZ) and 2 (321) and carry 1 which will add to give 12 where we will take 2 in answer and 1 as carry, Coming to the 3rd rightmost digit of both strings which is 0 (0ZZ) and 3 (321) and carrying 1 will add to give 4Input: str1 = ABC, str2 = 001
Output: ABD
Explanation: Again Starting from the left of both the strings which are C (ABC) and 1 (001) which will add to give D, then B+0 = B, then A+0 = A by basic math property.
Approach: The basic way to solve the problem is as follows:
- First we will make the length of the strings equal by adding ‘0’ in the small string.
- Then we will iterate through the string but from right to left just like a mathematical addition.
- After that we will be adding strings where 0-9 is same but A will be treated as 10, B will be treated as 11 and so on till Z as 35, if we get the sum exceeding 35 then we will be restart the digits from 0 and increment the carry by 1.
Below is the implementation of the above idea.
C++
// C++ code for the above approach: #include <algorithm> #include <iostream> using namespace std; string SumStr(string str1, string str2) { // Find the maximum length of the two input strings // And pad them with '0' to make them equal int max_len = max(str1.length(), str2.length()); str1.insert(0, max_len - str1.length(), '0' ); str2.insert(0, max_len - str2.length(), '0' ); // Initialize the result string string answer = ""; // Initialize the carry variable int carry = 0; // Iterate through the strings from right to left for ( int i = max_len - 1; i >= 0; i--) { // Determine the numeric value of the current // character int str1Val; if ( isdigit (str1[i])) { // If it's a digit, convert it to an integer str1Val = str1[i] - '0' ; } else { // If it's a letter (A to Z), // convert it to a numeric value (10 to 35) str1Val = str1[i] - 'A' + 10; } // Determine the numeric value of the current // character int str2Val; if ( isdigit (str2[i])) { // If it's a digit, convert it to an integer str2Val = str2[i] - '0' ; } else { // If it's a letter (A to Z), // Convert it to a numeric value (10 to 35) str2Val = str2[i] - 'A' + 10; } // Calculate the sum of the current digits along // with the carry int digitSum = str1Val + str2Val + carry; // Update the carry for the next iteration carry = digitSum / 36; // Ensure that the result is within the range of 0 // to 35 digitSum = digitSum % 36; // If the result is less than 10, if (digitSum < 10) { // Add it as a digit to the answer answer = char (digitSum + '0' ) + answer; } else { // If the result is 10 to 35, // Add it as a letter (A to Z) to the answer answer = char (digitSum - 10 + 'A' ) + answer; } } // If there is a carry left after processing, // Add it to the answer if (carry > 0) { answer = to_string(carry) + answer; } return answer; } // Driver Code int main() { string str1 = "ZZ"; string str2 = "321"; // Call the SumStr function // and print the result cout << SumStr(str1, str2) << endl; return 0; } |
Java
// Java Implementation import java.util.*; public class SumStrings { public static String sumStr(String str1, String str2) { // Find the maximum length of the two input strings // And pad them with '0' to make them equal int maxLen = Math.max(str1.length(), str2.length()); str1 = padString(str1, maxLen); str2 = padString(str2, maxLen); // Initialize the result string StringBuilder answer = new StringBuilder(); // Initialize the carry variable int carry = 0 ; // Iterate through the strings from right to left for ( int i = maxLen - 1 ; i >= 0 ; i--) { // Determine the numeric value of the current character int str1Val = getNumericValue(str1.charAt(i)); int str2Val = getNumericValue(str2.charAt(i)); // Calculate the sum of the current digits along with the carry int digitSum = str1Val + str2Val + carry; // Update the carry for the next iteration carry = digitSum / 36 ; // Ensure that the result is within the range of 0 to 35 digitSum = digitSum % 36 ; // If the result is less than 10, if (digitSum < 10 ) { // Add it as a digit to the answer answer.insert( 0 , digitSum); } else { // If the result is 10 to 35, // Add it as a letter (A to Z) to the answer answer.insert( 0 , ( char ) (digitSum - 10 + 'A' )); } } // If there is a carry left after processing, // Add it to the answer if (carry > 0 ) { answer.insert( 0 , carry); } return answer.toString(); } private static String padString(String str, int length) { StringBuilder paddedStr = new StringBuilder(str); while (paddedStr.length() < length) { paddedStr.insert( 0 , '0' ); } return paddedStr.toString(); } private static int getNumericValue( char c) { if (Character.isDigit(c)) { // If it's a digit, convert it to an integer return Character.getNumericValue(c); } else { // If it's a letter (A to Z), // convert it to a numeric value (10 to 35) return c - 'A' + 10 ; } } public static void main(String[] args) { String str1 = "ZZ" ; String str2 = "321" ; // Call the sumStr function and print the result System.out.println(sumStr(str1, str2)); } } // This code is contributed by Tapesh(tapeshdua42) |
Python3
# Python3 implementation # of above approach def SumStr(str1, str2): # Find the max len of the 2 input strings # And pad them with '0' to make them equal max_len = max ( len (str1), len (str2)) str1 = str1.zfill(max_len) str2 = str2.zfill(max_len) # Initialize the result string answer = "" # Initialize the carry variable carry = 0 # Iterate through the strings from right to left for i in range ( len (str2) - 1 , - 1 , - 1 ): # Determine the numeric value of the current character # In string 'str1' if str1[i].isdigit(): # If it's a digit, convert it to an integer str1Val = int (str1[i]) else : # If it's a letter (A to Z), # Convert it to a numeric value (10 to 35) str1Val = ord (str1[i]) - 55 # Determine the numeric value of the current character # In string 'str2' if str2[i].isdigit(): # If it's a digit, convert it to an integer str2Val = int (str2[i]) else : # If it's a letter (A to Z), # Convert it to a numeric value (10 to 35) str2Val = ord (str2[i]) - 55 # Calculate the sum of the current digits # Along with the carry digitSum = str1Val + str2Val + carry # Update the carry for the next iteration carry = digitSum / / 36 # Ensure that the result is within the range of 0 to 35 digitSum = digitSum % 36 # If the result is less than 10, if digitSum < 10 : # Add it as a digit to the answer answer = str (digitSum) + answer else : # If the result is 10 to 35, # Add it as a letter (A to Z) to the answer answer = chr (digitSum + 55 ) + answer # If there is a carry left after processing, # Add it to the answer if carry > 0 : answer = str (carry) + answer return answer # Driver Code str1 = 'ZZ' str2 = '321' # Call the sumStr function # and print the result print (SumStr(str1, str2)) # This code is contributed by the Author |
C#
using System; class Program { // Function to add two strings representing numbers in base-36 static string SumStr( string str1, string str2) { // Find the maximum length of the two input strings // and pad them with '0' to make them equal int maxLength = Math.Max(str1.Length, str2.Length); str1 = str1.PadLeft(maxLength, '0' ); str2 = str2.PadLeft(maxLength, '0' ); // Initialize the result string string answer = "" ; // Initialize the carry variable int carry = 0; // Iterate through the strings from right to left for ( int i = maxLength - 1; i >= 0; i--) { // Determine the numeric value of the current character int str1Val; if ( char .IsDigit(str1[i])) { str1Val = str1[i] - '0' ; } else { str1Val = str1[i] - 'A' + 10; } // Determine the numeric value of the current character int str2Val; if ( char .IsDigit(str2[i])) { str2Val = str2[i] - '0' ; } else { str2Val = str2[i] - 'A' + 10; } // Calculate the sum of the current digits along with the carry int digitSum = str1Val + str2Val + carry; // Update the carry for the next iteration carry = digitSum / 36; // Ensure that the result is within the range of 0 to 35 digitSum = digitSum % 36; // If the result is less than 10, add it as a digit to the answer if (digitSum < 10) { answer = ( char )(digitSum + '0' ) + answer; } else { // If the result is 10 to 35, add it as a letter (A to Z) to the answer answer = ( char )(digitSum - 10 + 'A' ) + answer; } } // If there is a carry left after processing, add it to the answer if (carry > 0) { answer = carry.ToString() + answer; } return answer; } static void Main() { string str1 = "ZZ" ; string str2 = "321" ; // Call the SumStr function and print the result Console.WriteLine(SumStr(str1, str2)); } } |
Javascript
// JavaScript code for the above approach: function SumStr(str1, str2) { // Find the maximum length of the two input strings // and pad them with '0' to make them equal const maxLen = Math.max(str1.length, str2.length); str1 = str1.padStart(maxLen, '0' ); str2 = str2.padStart(maxLen, '0' ); // Initialize the result string let answer = '' ; // Initialize the carry variable let carry = 0; // Iterate through the strings from right to left for (let i = maxLen - 1; i >= 0; i--) { // Determine the numeric value of the current character const str1Val = isDigit(str1[i]) ? parseInt(str1[i]) : str1.charCodeAt(i) - 'A' .charCodeAt(0) + 10; const str2Val = isDigit(str2[i]) ? parseInt(str2[i]) : str2.charCodeAt(i) - 'A' .charCodeAt(0) + 10; // Calculate the sum of the current digits along with the carry let digitSum = str1Val + str2Val + carry; // Update the carry for the next iteration carry = Math.floor(digitSum / 36); // Ensure that the result is within the range of 0 to 35 digitSum = digitSum % 36; if (digitSum < 10) { // If the result is less than 10, // add it as a digit to the answer answer = String.fromCharCode(digitSum + '0' .charCodeAt(0)) + answer; } else { // If the result is 10 to 35, add it as // a letter (A to Z) to the answer answer = String.fromCharCode(digitSum - 10 + 'A' .charCodeAt(0)) + answer; } } // If there is a carry left after processing, add it to the answer if (carry > 0) { answer = carry.toString() + answer; } return answer; } function isDigit(char) { return !isNaN(char) && !isNaN(parseInt(char)); } // Driver code const str1 = "ZZ" ; const str2 = "321" ; // Call the SumStr function and print the result console.log(SumStr(str1, str2)); |
420
Time Complexity: O(N),
Auxiliary Space: O(N), where N is the length of the string.