Add two integers of different base and represent sum in smaller base of the two
Given two integers X, Y in base B1 and B2 respectively, the task is to find the sum of integers X and Y and represent the result in min of ( B1 and B2 ).
Example:
Input: X = 123, Y = 234, B1 = 6, B2 = 8
Output: 543
Explanation:
Integer in base 10: 51 and 156
Sum of Integers: 207
Minimum Base: 6
Sum of Integer in Base 6 = 543Input: X = 16, Y = 24, B1 = 9, B2 = 7
Output: 45
Explanation:
Minimum Base: 7
Integer in base 7: 21 and 24
Sum of Integer in Base 6 –
?? 2 1
+?? 2 4
—————-
?? 4 5
Approach 1: The idea is to convert both integers in base 10 ( decimal ) using Base Conversion, then find the sum of the two numbers. The sum is then converted into smaller base B ( minimum of B1 and B2 ) using Base Conversion.
Below is the implementation of the above approach:
C++
// Program to find the// sum of two integers of// different bases.#include <bits/stdc++.h>using namespace std;int val(char c){ if (c >= '0' && c <= '9') return (int)c - '0'; else return (int)c - 'A' + 10;}int convert(string num, int base){ int len = (num.size()); // Initialize power of base int power = 1; // Initialize result int res = 0; int i; // Decimal equivalent is str[len-1]*1 + // str[len-2]*base + str[len-3]*(base^2) + ... for(i = len - 1; i >= 0; i--) { res += val(num[i]) * power; power = power * base; } return res;}int dec_to_base(int num, int base){ // Maximum base - 36 string base_num = ""; while (num > 0) { int dig = int(num % base); if (dig < 10) base_num += to_string(dig); else base_num += to_string('A' + dig - 10); num /= base; } // To reverse the string reverse(base_num.begin(), base_num.end()); return stoi(base_num);}// Driver Codeint main(){ string a = "123"; string b = "234"; int base_a = 6; int base_b = 8; // Integer in base 10 int a10 = convert(a, base_a); int b10 = convert(b, base_b); // Sum of integers int summ = a10 + b10; // uncomment to check // intermediate value // of a and b to base 10 // print(a10, b10) // Minimum Base int min_base = min(base_a, base_b); // Sum of integers in Min Base cout << (dec_to_base(summ, min_base));}// This code is contributed by grand_master |
Java
// Java Program to find the// sum of two integers of// different bases.import java.util.*;class GFG { static int val(char c) { if (c >= '0' && c <= '9') return (int)c - '0'; else return (int)c - 'A' + 10; } static int convert(String num, int bases) { int len = (num.length()); // Initialize power of base int power = 1; // Initialize result int res = 0; int i; // Decimal equivalent is str[len-1]*1 + // str[len-2]*base + str[len-3]*(base^2) + ... for (i = len - 1; i >= 0; i--) { res += val(num.charAt(i)) * power; power = power * bases; } return res; } static void dec_to_base(int num, int bases) { // Maximum base - 36 // String base_num = ""; StringBuilder base_num = new StringBuilder(); while (num > 0) { int dig = (num % bases); if (dig < 10) base_num.append(String.valueOf(dig)); else base_num.append( String.valueOf(('A' + dig - 10))); num /= bases; } // print ans in reverse order for (int i = base_num.length() - 1; i >= 0; i--) System.out.print(base_num.charAt(i)); } // Driver Code public static void main(String[] args) { String a = "123"; String b = "234"; int base_a = 6; int base_b = 8; // Integer in base 10 int a10 = convert(a, base_a); int b10 = convert(b, base_b); // Sum of integers int summ = a10 + b10; // uncomment to check // intermediate value // of a and b to base 10 // print(a10, b10) // Minimum Base int min_base = Math.min(base_a, base_b); // Sum of integers in Min Base dec_to_base(summ, min_base); }}// This code is contributed by ukasp. |
Python
# Program to find the # sum of two integers of # different bases. # Base conversiondef dec_to_base(num, base): # Maximum base - 36 base_num = "" while num > 0: dig = int(num % base) if dig < 10: base_num += str(dig) else: # Using uppercase letters base_num += chr(ord('A') + dig - 10 ) num //= base # To reverse the string base_num = base_num[::-1] return int(base_num) # Driver Code a = '123'b = '234'base_a = 6base_b = 8# Integer in base 10a10 = int(a, base_a)b10 = int(b, base_b)# Sum of integers summ = a10 + b10; # uncomment to check # intermediate value # of a and b to base 10# print(a10, b10)# Minimum Basemin_base = min(base_a, base_b)# Sum of integers in Min Baseprint(dec_to_base(summ, min_base)) |
C#
// C# Program to find the// sum of two integers of// different bases.using System.Collections.Generic; using System;using System.Linq;using System.Text;class GFG {static int val(char c){ if (c >= '0' && c <= '9') return (int)c - '0'; else return (int)c - 'A' + 10;}static int convert(string num,int bases){ int len = (num.Length); // Initialize power of base int power = 1; // Initialize result int res = 0; int i; // Decimal equivalent is str[len-1]*1 + // str[len-2]*base + str[len-3]*(base^2) + ... for(i = len - 1; i >= 0; i--) { res += val(num[i]) * power; power = power * bases; } return res;}static void dec_to_base(int num, int bases){ // Maximum base - 36 // String base_num = ""; var base_num = new StringBuilder(); while (num > 0) { int dig = (num % bases); if (dig < 10) base_num .Append(dig.ToString()); else base_num .Append( ('A' + dig - 10).ToString()); num /= bases; } // print ans in reverse order for(int i = base_num.Length - 1; i >= 0; i--) Console.Write(base_num[i]);}// Driver Codepublic static void Main(String[] args) { String a = "123"; String b = "234"; int base_a = 6; int base_b = 8; // Integer in base 10 int a10 = convert(a, base_a); int b10 = convert(b, base_b); // Sum of integers int summ = a10 + b10; // uncomment to check // intermediate value // of a and b to base 10 // print(a10, b10) // Minimum Base int min_base = Math.Min(base_a, base_b); // Sum of integers in Min Base dec_to_base(summ, min_base);}}// This code is contributed by amreshkumar3 |
Javascript
<script>// Javascript Program to find the// sum of two integers of// different bases.function val(c){ if (c >= '0' && c <= '9') return c.charCodeAt(0) - '0'.charCodeAt(0); else return c.charCodeAt(0) - 'A'.charCodeAt(0) + 10;}function convert(num,bases){ let len = (num.length); // Initialize power of base let power = 1; // Initialize result let res = 0; let i; // Decimal equivalent is str[len-1]*1 + // str[len-2]*base + str[len-3]*(base^2) + ... for (i = len - 1; i >= 0; i--) { res += val(num[i]) * power; power = power * bases; } return res;}function dec_to_base(num,bases){ // Maximum base - 36 // String base_num = ""; let base_num = []; while (num > 0) { let dig = (num % bases); if (dig < 10) base_num.push((dig).toString()); else base_num.append( ('A'.charCodeAt(0) + dig - 10).toString()); num = Math.floor(num/bases); } // print ans in reverse order for (let i = base_num.length - 1; i >= 0; i--) document.write(base_num[i]);} // Driver Code let a = "123"; let b = "234"; let base_a = 6; let base_b = 8; // Integer in base 10 let a10 = convert(a, base_a); let b10 = convert(b, base_b); // Sum of integers let summ = a10 + b10; // uncomment to check // intermediate value // of a and b to base 10 // print(a10, b10) // Minimum Base let min_base = Math.min(base_a, base_b); // Sum of integers in Min Base dec_to_base(summ, min_base);// This code is contributed by avanitrachhadiya2155</script> |
Output:
543
Time Complexity: O(logN)
Auxiliary Space: O(1)
Approach 2: We can reduce the number of conversions from the previous approach. Here we need to find the smaller base B ( minimum of B1 and B2 ), then convert the integer with a larger base to smaller base B and add the integers with help of the Addition of two integers of given base.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Program to find the// sum of two integers of// different bases.// Base conversionint dec_to_base(int num, int base){ // Maximum base - 36 string base_num = ""; while(num > 0){ int dig = ((num % base) + base) % base; if(dig < 10) base_num += to_string(dig); else{ // Using uppercase letters base_num += ('A' + (dig - 10)); } num = (num/base); } // To reverse the string reverse(base_num.begin(), base_num.end()); return stoi(base_num);}// Function to find the sum of// two integers of base Bstring sumBase(string a, string b, int base){ int len_a = a.length(); int len_b = b.length(); string s = ""; string sum = ""; int diff = abs(len_a - len_b); // Padding 0 in front of the // number to make both numbers equal for(int i = 1; i < diff + 1; i++){ s += "0"; } // Condition to check if the strings // have lengths mis-match if (len_a < len_b) a = s + a; else b = s + b; int carry = 0; // Loop to find the find the sum // of two integers of base B for(int i = max(len_a, len_b) - 1; i >= 0; i--){ // Current Place value for // the resultant sum int a1 = a[i] - '0'; int b1 = b[i] - '0'; int curr = carry + a1 + b1; // Update carry carry = (curr / base); // Find current digit curr = (curr % base + base) % base; // Update sum result sum = to_string(curr) + sum; } if (carry > 0) sum = to_string(carry) + sum; return sum;}// Driver Codeint main(){ string a = "123"; string b = "234"; int base_a = 6; int base_b = 8; int min_Base = 0; // Convert the integer with // large base to smaller base B if(base_a > base_b){ min_Base = base_b; int a10 = stoi(a, 0, base_a); a = dec_to_base(a10, base_b); } else{ min_Base = base_a; int b10 = stoi(b, 0, base_b); b = dec_to_base(b10, base_a); } // Sum of Integer in min_Base string sum = sumBase(a, b, min_Base); cout << sum << endl;}// This code is contributed by phasing17 |
Java
// Java code for the above approachimport java.util.*;class GFG { // Program to find the // sum of two integers of // different bases. // Method to reverse a String static String Reverse(String s) { // create a StringBuilder object StringBuilder sb = new StringBuilder(); //append s to sb sb.append(s); // reverse sb sb.reverse(); return new String(sb); } // base conversion static int dec_to_base(int num, int base1) { // Maximum base - 36 String base_num = ""; while (num > 0) { int dig = ((num % base1) + base1) % base1; if (dig < 10) base_num += String.valueOf(dig); else { // Using uppercase letters base_num += ('A' + (dig - 10)); } num = (num / base1); } // To reverse the String base_num = Reverse(base_num); return Integer.valueOf(base_num); } // Function to find the sum of // two integers of base1 B static String sumBase(String a, String b, int base1) { int len_a = a.length(); int len_b = b.length(); String s = ""; String sum = ""; int diff = Math.abs(len_a - len_b); // Padding 0 in front of the // number to make both numbers equal for (int i = 1; i < diff + 1; i++) { s += "0"; } // Condition to check if the Strings // have lengths mis-match if (len_a < len_b) a = s + a; else b = s + b; int carry = 0; // Loop to find the find the sum // of two integers of base1 B for (int i = Math.max(len_a, len_b) - 1; i >= 0; i--) { // Current Place value for // the resultant sum int a1 = a.charAt(i) - '0'; int b1 = b.charAt(i) - '0'; int curr = carry + a1 + b1; // Update carry carry = (curr / base1); // Find current digit curr = (curr % base1 + base1) % base1; // Update sum result sum = String.valueOf(curr) + sum; } if (carry > 0) sum = String.valueOf(carry) + sum; return sum; } // Driver Code public static void main(String[] args) { String a = "123"; String b = "234"; int base_a = 6; int base_b = 8; int min_Base = 0; // Convert the integer with // large base1 to smaller base1 B if (base_a > base_b) { min_Base = base_b; int a10 = Integer.valueOf(a, base_a); a = String.valueOf(dec_to_base(a10, base_b)); } else { min_Base = base_a; int b10 = Integer.valueOf(b, base_b); b = String.valueOf(dec_to_base(b10, base_a)); } // Sum of Integer in min_Base String sum = sumBase(a, b, min_Base); System.out.println(sum); }}// This code is contributed by phasing17 |
Python3
# Program to find the# sum of two integers of# different bases.# Base conversiondef dec_to_base(num, base): # Maximum base - 36 base_num = "" while num > 0: dig = int(num % base) if dig < 10: base_num += str(dig) else: # Using uppercase letters base_num += chr(ord('A') + dig - 10) num //= base # To reverse the string base_num = base_num[::-1] return int(base_num) # Function to find the sum of# two integers of base Bdef sumBase(a, b, base): len_a = len(a) len_b = len(b) s = "" sum = "" diff = abs(len_a - len_b) # Padding 0 in front of the # number to make both numbers equal for i in range(1, diff + 1): s += "0" # Condition to check if the strings # have lengths mis-match if (len_a < len_b): a = s + a else: b = s + b carry = 0 # Loop to find the find the sum # of two integers of base B for i in range(max(len_a, len_b) - 1, -1, -1): # Current Place value for # the resultant sum curr = carry + (ord(a[i]) - ord('0'))\ + (ord(b[i]) - ord('0')) # Update carry carry = curr // base # Find current digit curr = curr % base # Update sum result sum = chr(curr + ord('0')) + sum if (carry > 0): sum = chr(carry + ord('0')) + sum return sum# Driver Codea = '123'b = '234'base_a = 6base_b = 8# Convert the integer with# large base to smaller base Bif base_a > base_b: min_Base = base_b a10 = int(a, base_a) a = dec_to_base(a10, base_b)else: min_Base = base_a b10 = int(b, base_b) b = dec_to_base(b10, base_a)# Sum of Integer in min_Basesum = sumBase(str(a), str(b), min_Base)print(sum) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Program to find the // sum of two integers of // different bases. // Method to reverse a string static string Reverse(string s) { char[] charArray = s.ToCharArray(); Array.Reverse(charArray); return new string(charArray); } // base conversion static int dec_to_base(int num, int base1) { // Maximum base - 36 string base_num = ""; while (num > 0) { int dig = ((num % base1) + base1) % base1; if (dig < 10) base_num += Convert.ToString(dig); else { // Using uppercase letters base_num += ('A' + (dig - 10)); } num = (num / base1); } // To reverse the string base_num = Reverse(base_num); return Convert.ToInt32(base_num); } // Function to find the sum of // two integers of base1 B static string sumBase(string a, string b, int base1) { int len_a = a.Length; int len_b = b.Length; string s = ""; string sum = ""; int diff = Math.Abs(len_a - len_b); // Padding 0 in front of the // number to make both numbers equal for (int i = 1; i < diff + 1; i++) { s += "0"; } // Condition to check if the strings // have lengths mis-match if (len_a < len_b) a = s + a; else b = s + b; int carry = 0; // Loop to find the find the sum // of two integers of base1 B for (int i = Math.Max(len_a, len_b) - 1; i >= 0; i--) { // Current Place value for // the resultant sum int a1 = a[i] - '0'; int b1 = b[i] - '0'; int curr = carry + a1 + b1; // Update carry carry = (curr / base1); // Find current digit curr = (curr % base1 + base1) % base1; // Update sum result sum = Convert.ToString(curr) + sum; } if (carry > 0) sum = Convert.ToString(carry) + sum; return sum; } // Driver Code public static void Main(string[] args) { string a = "123"; string b = "234"; int base_a = 6; int base_b = 8; int min_Base = 0; // Convert the integer with // large base1 to smaller base1 B if (base_a > base_b) { min_Base = base_b; int a10 = Convert.ToInt32(a, base_a); a = Convert.ToString(dec_to_base(a10, base_b)); } else { min_Base = base_a; int b10 = Convert.ToInt32(b, base_b); b = Convert.ToString(dec_to_base(b10, base_a)); } // Sum of Integer in min_Base string sum = sumBase(a, b, min_Base); Console.WriteLine(sum); }}// This code is contributed by phasing17 |
Javascript
<script>b// JavaScript code for the above approach// Program to find the// sum of two integers of// different bases.// Base conversionfunction dec_to_base(num, base){ // Maximum base - 36 let base_num = "" while(num > 0){ let dig = parseInt(num % base) if(dig < 10) base_num += dig.toString() else{ // Using uppercase letters base_num += String.fromCharCode('A'.charCodeAt(0) + dig - 10) } num = Math.floor(num/base) } // To reverse the string base_num = base_num.split("").reverse().join("") return parseInt(base_num)}// Function to find the sum of// two integers of base Bfunction sumBase(a, b, base){ let len_a = a.length let len_b = b.length let s = "" let sum = "" let diff = Math.abs(len_a - len_b) // Padding 0 in front of the // number to make both numbers equal for(let i=1;i<diff+1;i++){ s += "0" } // Condition to check if the strings // have lengths mis-match if (len_a < len_b) a = s + a else b = s + b let carry = 0 // Loop to find the find the sum // of two integers of base B for(let i = Math.max(len_a, len_b) - 1;i>=0;i--){ // Current Place value for // the resultant sum let curr = carry + (a.charCodeAt(i) - '0'.charCodeAt(0)) + (b.charCodeAt(i) - '0'.charCodeAt(0)) // Update carry carry = Math.floor(curr / base) // Find current digit curr = curr % base // Update sum result sum = String.fromCharCode(curr + '0'.charCodeAt(0)) + sum } if (carry > 0) sum = String.fromCharCode(carry + '0'.charCodeAt(0)) + sum return sum}// Driver Codelet a = '123'let b = '234'let base_a = 6let base_b = 8let min_Base = 0// Convert the integer with// large base to smaller base Bif(base_a > base_b){ min_Base = base_b let a10 = parseInt(a, base_a) a = dec_to_base(a10, base_b)}else{ min_Base = base_a let b10 = parseInt(b, base_b) b = dec_to_base(b10, base_a)}// Sum of Integer in min_Baselet sum = sumBase(a.toString(), b.toString(), min_Base)document.write(sum,"</br>")// This code is contributed by shinjanpatra</script> |
Output:
543
Time Complexity: O(logN)
Auxiliary Space: O(1)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
