Multiply two numbers of different base and represent product in another given base

0 0 8 minutes read

Given two numbers N, M in the bases X, Y and another base P. The task is to find the product of N and M and represent the product in base P.

Examples:

Input: N = 101, M = 110, X = 2, Y = 2, P = 16
Output:1E
Explanation: N_X * M_Y = (101)₂ * (110)₂ = (11110)₂
(11110)₂ = (1E)₁₆

Input: N = 101, M = A, X = 2, Y = 20, P = 16
Output: 32
Explanation: N_x = (101)₂ = (5)₂₀
N_X * M_Y = (5)₂₀ * (A)₂₀ = (2A)₂₀
(2A)₂₀ = (32)₁₆

Approach: The approach is to convert the given numbers in decimal, perform the product and then turn it back to a number of base p. Follow the steps mentioned below:

Convert N_X and M_Y to decimal number.
Perform multiplication on the decimal numbers.
Convert the result of multiplication from decimal to base P.

Below is the implementation of the above approach.

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Convert Number from a given base
// to decimal
// Return the value of a char.
static int value(char c)
{
  if (c >= '0' && c <= '9')
    return (int)c - '0';
  else
    return (int)c - 'A' + 10;
}
 
// Function to convert a
// number from given base to decimal
int toDecimal(string s, int base)
{
  int length = s.length();
 
  // Initialize power of base and result
  int power = 1, ans = 0;
 
  // Decimal equivalent of s
  for (int i = length - 1; i >= 0; i--)
  {
    ans += value(s[i]) * power;
    power = power * base;
  }
 
  return ans;
}
 
// Function to convert decimal
// to any given base
char reverseValue(int n)
{
  if (n >= 0 && n <= 9)
    return (char)(n + 48);
  else
    return (char)(n - 10 + 65);
}
 
// Function to convert a given
// decimal number to a base 'base'
string toBase(int base, int num)
{
  string s = "";
 
  // Convert input number is given
  // base by repeatedly dividing it
  // by base and taking remainder
  while (num > 0)
  {
    s += reverseValue(num % base);
    num /= base;
  }
  string sb = "";
 
  // Append a string into StringBuilder
  sb += (s);
 
  // Reverse the result
  reverse(sb.begin(), sb.end());
  return sb;
}
 
// Function to find
// the product of N and M
void findProduct(string N, int X,
                 string M,
                 int Y, int P)
{
 
  // Convert N to decimal
  int decimalX = toDecimal(N, X);
 
  // Convert y to decimal
  int decimalY = toDecimal(M, Y);
 
  // Multiply the decimal numbers
  int product = decimalX * decimalY;
 
  // Convert product to base
  string result = toBase(P, product);
 
  // Print the result
  cout << (result);
}
 
// Driver code
int main()
{
  string N = "101", M = "110";
  int X = 2, Y = 2, P = 16;
  findProduct(N, X, M, Y, P);
  return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java code to implement above approach
import java.io.*;
 
class GFG {
     
    // Function to find 
    // the product of N and M
    static void findProduct(String N, int X, 
                            String M,
                            int Y, int P)
    {
 
        // Convert N to decimal
        int decimalX = toDecimal(N, X);
 
        // Convert y to decimal
        int decimalY = toDecimal(M, Y);
 
        // Multiply the decimal numbers
        int product = decimalX * decimalY;
 
        // Convert product to base
        String result = toBase(P, product);
 
        // Print the result
        System.out.println(result);
    }
 
    // Convert Number from a given base 
    // to decimal
    // Return the value of a char.
    static int value(char c)
    {
        if (c >= '0' && c <= '9')
            return (int)c - '0';
        else
            return (int)c - 'A' + 10;
    }
 
    // Function to convert a
    // number from given base to decimal
    static int toDecimal(String s, int base)
    {
        int length = s.length();
 
        // Initialize power of base and result
        int power = 1, ans = 0;
 
        // Decimal equivalent of s
        for (int i = length - 1; i >= 0; i--) {
            ans += value(s.charAt(i)) * power;
            power = power * base;
        }
 
        return ans;
    }
 
    // Function to convert decimal 
    // to any given base
    static char reverseValue(int n)
    {
        if (n >= 0 && n <= 9)
            return (char)(n + 48);
        else
            return (char)(n - 10 + 65);
    }
 
    // Function to convert a given 
    // decimal number to a base 'base'
    static String toBase(int base, int num)
    {
        String s = "";
 
        // Convert input number is given
        // base by repeatedly dividing it
        // by base and taking remainder
        while (num > 0) {
            s += reverseValue(num % base);
            num /= base;
        }
        StringBuilder sb = new StringBuilder();
 
        // Append a string into StringBuilder
        sb.append(s);
 
        // Reverse the result
        return new String(sb.reverse());
    }
     
    // Driver code
    public static void main(String[] args)
    {
        String N = "101", M = "110";
        int X = 2, Y = 2, P = 16;
        findProduct(N, X, M, Y, P);
    }
}

Python3

# Python code for the above approach
 
# Convert Number from a given base
# to decimal
# Return the value of a char.
def value(c):
 
  if (ord(c[0]) >= ord('0') and ord(c) <= ord('9')):
    return int(c)
  else:
    return ord(c[0]) - ord('A')  + 10
 
# Function to convert a
# number from given base to decimal
def toDecimal(s,base):
 
  length = len(s)
 
  # Initialize power of base and result
  power,ans = 1,0
 
  # Decimal equivalent of s
  for i in range(length-1,-1,-1):
 
    ans += value(s[i]) * power
    power = power * base
 
  return ans
 
# Function to convert decimal
# to any given base
def reverseValue(n):
 
  if (n >= 0 and n <= 9):
    return chr(n + 48)
  else:
    return chr(n - 10 + 65)
 
# Function to convert a given
# decimal number to a base 'base'
def toBase(base, num):
 
  s = ""
 
  # Convert input number is given
  # base by repeatedly dividing it
  # by base and taking remainder
  while (num > 0):
 
    s += reverseValue(num % base)
    num = (num//base)
 
  sb = ""
 
  # Append a string into StringBuilder
  sb += (s)
 
  # Reverse the result
  sb = sb[::-1]
  return sb
 
# Function to find
# the product of N and M
def findProduct(N, X, M, Y, P):
 
  # Convert N to decimal
  decimalX = toDecimal(N, X)
 
  # Convert y to decimal
  decimalY = toDecimal(M, Y)
 
  # Multiply the decimal numbers
  product = decimalX * decimalY
 
  # Convert product to base
  result = toBase(P, product)
 
  # Print the result
  print(result)
 
# Driver code
N, M = "101", "110"
X, Y, P = 2, 2, 16
findProduct(N, X, M, Y, P)
 
# This code is contributed by shinjanpatra

C#

// C# code to implement above approach
using System;
class GFG
{
 
  // Function to find 
  // the product of N and M
  static void findProduct(String N, int X,
                          String M,
                          int Y, int P)
  {
 
    // Convert N to decimal
    int decimalX = toDecimal(N, X);
 
    // Convert y to decimal
    int decimalY = toDecimal(M, Y);
 
    // Multiply the decimal numbers
    int product = decimalX * decimalY;
 
    // Convert product to base
    String result = toBase(P, product);
 
    // Print the result
    Console.Write(result);
  }
 
  // Convert Number from a given base 
  // to decimal
  // Return the value of a char.
  static int value(char c)
  {
    if (c >= '0' && c <= '9')
      return (int)c - '0';
    else
      return (int)c - 'A' + 10;
  }
 
  // Function to convert a
  // number from given base to decimal
  static int toDecimal(String s, int _base)
  {
    int length = s.Length;
 
    // Initialize power of base and result
    int power = 1, ans = 0;
 
    // Decimal equivalent of s
    for (int i = length - 1; i >= 0; i--)
    {
      ans += value(s[i]) * power;
      power = power * _base;
    }
 
    return ans;
  }
 
  // Function to convert decimal 
  // to any given base
  static char reverseValue(int n)
  {
    if (n >= 0 && n <= 9)
      return (char)(n + 48);
    else
      return (char)(n - 10 + 65);
  }
 
  // Function to convert a given 
  // decimal number to a base 'base'
  static String toBase(int _base, int num)
  {
    String s = "";
 
    // Convert input number is given
    // base by repeatedly dividing it
    // by base and taking remainder
    while (num > 0)
    {
      s += reverseValue(num % _base);
      num /= _base;
    }
    String sb = "";
 
    // Append a string into StringBuilder
    sb += s;
 
    // Reverse the result
    char[] arr = sb.ToCharArray();
    Array.Reverse(arr);
    return new string(arr);
  }
 
  // Driver code
  public static void Main()
  {
    String N = "101", M = "110";
    int X = 2, Y = 2, P = 16;
    findProduct(N, X, M, Y, P);
  }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
 
// JavaScript code for the above approach
 
 
// Convert Number from a given base
// to decimal
// Return the value of a char.
function value(c)
{
if (c.charCodeAt(0) >= '0'.charCodeAt(0) && c.charCodeAt(0) <= '9'.charCodeAt(0))
    return parseInt(c);
else
    return c.charCodeAt(0) - 'A'.charCodeAt(0) + 10;
}
 
// Function to convert a
// number from given base to decimal
function toDecimal(s,base)
{
let length = s.length;
 
// Initialize power of base and result
let power = 1, ans = 0;
 
// Decimal equivalent of s
for (let i = length - 1; i >= 0; i--)
{
    ans += value(s[i]) * power;
    power = power * base;
}
 
return ans;
}
 
// Function to convert decimal
// to any given base
function reverseValue(n)
{
if (n >= 0 && n <= 9)
    return String.fromCharCode(n + 48);
else
    return String.fromCharCode(n - 10 + 65);
}
 
// Function to convert a given
// decimal number to a base 'base'
function toBase(base, num)
{
let s = "";
 
// Convert input number is given
// base by repeatedly dividing it
// by base and taking remainder
while (num > 0)
{
    s += reverseValue(num % base);
    num = Math.floor(num/base);
}
let sb = "";
 
// Append a string into StringBuilder
sb += (s);
 
// Reverse the result
sb = sb.split("").reverse().join("");
return sb;
}
 
// Function to find
// the product of N and M
function findProduct(N, X, M, Y, P)
{
 
// Convert N to decimal
let decimalX = toDecimal(N, X);
 
// Convert y to decimal
let decimalY = toDecimal(M, Y);
 
// Multiply the decimal numbers
let product = decimalX * decimalY;
 
// Convert product to base
let result = toBase(P, product);
 
// Print the result
document.write(result,"</br>");
}
 
// Driver code
 
let N = "101", M = "110";
let X = 2, Y = 2, P = 16;
findProduct(N, X, M, Y, P);
 
// This code is contributed by shinjanpatra
 
</script>

Output

1E

Time Complexity: O(D) where D is the maximum number of digits in N, M and product
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!