Program to Subtract two integers of given base

0 0 7 minutes read

Given three positive integers X, Y, and B, where X and Y are Base-B integers, the task is to find the value of X – Y such that X >= Y.

Examples:

Input: X = 1212, Y = 256, B = 8
Output: 0734
Explanation: The value of 1212 – 256 in base 8 is 734.

Input: X = 546, Y = 248, B = 9
Output: 287

Approach: The given problem can be solved by using basic mathematics subtraction. Follow the steps below to solve the given problem:

Initialize two variables say power = 1, carry = 0, to keep track of current power and carry generated while subtracting respectively.
Initialize a variable, say finalVal = 0, to store the resultant value of X – Y.
Iterate a loop until X > 0 and perform the following steps:
- Store last digits from the current value of X and Y in two variables, say n1 = X % 10 and n2 = Y % 10 respectively.
- Remove last digits from X and Y by updating X = X / 10 and Y = Y / 10.
- Initialize temp = n1 – n2 + carry.
- If temp < 0, then add base B to N, that is N = N + B and set carry = -1, which will act as a borrow. Otherwise, set carry = 0.
- Add current temp * power to finalVal, that is finalVal = finalVal + temp * power and set power = power * 10.
After completing the above steps, print the value of finalVal as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find X - Y in base B
int getDifference(int B, int X, int Y)
{
 
    // To store final answer
    int finalVal = 0;
 
    // To store carry generated
    int carry = 0;
 
    // To keep track of power
    int power = 1;
 
    while (X > 0) {
 
        // Store last digits of current
        // value of X and Y in n1 and
        // n2 respectively
        int n1 = X % 10;
        int n2 = Y % 10;
 
        // Remove last digits from
        // X and Y
        X = X / 10;
        Y = Y / 10;
 
        int temp = n1 - n2 + carry;
 
        if (temp < 0) {
 
            // Carry = -1 will act
            // as borrow
            carry = -1;
            temp += B;
        }
 
        else {
            carry = 0;
        }
 
        // Add in final result
        finalVal += temp * power;
        power = power * 10;
    }
 
    // Return final result
    return finalVal;
}
 
// Driver Code
int main()
{
    int X = 1212;
    int Y = 256;
    int B = 8;
 
    cout << (getDifference(B, X, Y));
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Function to find X - Y in base B
    public static int getDifference(
        int B, int X, int Y)
    {
 
        // To store final answer
        int finalVal = 0;
 
        // To store carry generated
        int carry = 0;
 
        // To keep track of power
        int power = 1;
 
        while (X > 0) {
 
            // Store last digits of current
            // value of X and Y in n1 and
            // n2 respectively
            int n1 = X % 10;
            int n2 = Y % 10;
 
            // Remove last digits from
            // X and Y
            X = X / 10;
            Y = Y / 10;
 
            int temp = n1 - n2 + carry;
 
            if (temp < 0) {
 
                // Carry = -1 will act
                // as borrow
                carry = -1;
                temp += B;
            }
 
            else {
                carry = 0;
            }
 
            // Add in final result
            finalVal += temp * power;
            power = power * 10;
        }
 
        // Return final result
        return finalVal;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int X = 1212;
        int Y = 256;
        int B = 8;
 
        System.out.println(
            getDifference(B, X, Y));
    }
}

Python3

# Python3 program for the above approach
 
# Function to find X - Y in base B
def getDifference(B, X, Y) :
 
    # To store final answer
    finalVal = 0;
 
    # To store carry generated
    carry = 0;
 
    # To keep track of power
    power = 1;
 
    while (X > 0) :
 
        # Store last digits of current
        # value of X and Y in n1 and
        # n2 respectively
        n1 = X % 10;
        n2 = Y % 10;
 
        # Remove last digits from
        # X and Y
        X = X // 10;
        Y = Y // 10;
 
        temp = n1 - n2 + carry;
 
        if (temp < 0) :
 
            # Carry = -1 will act
            # as borrow
            carry = -1;
            temp += B;
 
        else :
            carry = 0;
 
        # Add in final result
        finalVal += temp * power;
        power = power * 10;
 
    # Return final result
    return finalVal;
 
# Driver Code
if __name__ == "__main__" :
 
    X = 1212;
    Y = 256;
    B = 8;
 
    print(getDifference(B, X, Y));
 
    # This code is contributed by AnkThon

C#

// C# program for the above approach
using System;
public class GFG
{
 
    // Function to find X - Y in base B
    public static int getDifference(int B, int X, int Y)
    {
 
        // To store final answer
        int finalVal = 0;
 
        // To store carry generated
        int carry = 0;
 
        // To keep track of power
        int power = 1;
 
        while (X > 0) {
 
            // Store last digits of current
            // value of X and Y in n1 and
            // n2 respectively
            int n1 = X % 10;
            int n2 = Y % 10;
 
            // Remove last digits from
            // X and Y
            X = X / 10;
            Y = Y / 10;
 
            int temp = n1 - n2 + carry;
 
            if (temp < 0) {
 
                // Carry = -1 will act
                // as borrow
                carry = -1;
                temp += B;
            }
 
            else {
                carry = 0;
            }
 
            // Add in final result
            finalVal += temp * power;
            power = power * 10;
        }
 
        // Return final result
        return finalVal;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int X = 1212;
        int Y = 256;
        int B = 8;
 
        Console.WriteLine(getDifference(B, X, Y));
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
// Javascript program for the above approach
 
// Function to find X - Y in base B
function getDifference(B, X, Y) {
  // To store final answer
  let finalVal = 0;
 
  // To store carry generated
  let carry = 0;
 
  // To keep track of power
  let power = 1;
 
  while (X > 0) {
    // Store last digits of current
    // value of X and Y in n1 and
    // n2 respectively
    let n1 = X % 10;
    let n2 = Y % 10;
 
    // Remove last digits from
    // X and Y
    X = Math.floor(X / 10);
    Y = Math.floor(Y / 10);
 
    let temp = n1 - n2 + carry;
 
    if (temp < 0) {
      // Carry = -1 will act
      // as borrow
      carry = -1;
      temp += B;
    } else {
      carry = 0;
    }
 
    // Add in final result
    finalVal += temp * power;
    power = power * 10;
  }
 
  // Return final result
  return finalVal;
}
 
// Driver Code
 
let X = 1212;
let Y = 256;
let B = 8;
 
document.write(getDifference(B, X, Y));
 
// This code is contributed by gfgking
 
</script>

Output:

Time Complexity: O(log₁₀N)
Auxiliary Space: O(1)

However, we can optimize the solution by performing the following steps:

First, convert the given numbers X and Y into decimal form.
Then, find the difference between X and Y.
Finally, convert the decimal difference back into the given base.

Here’s the implementation of the above approach:

C++

//C++ progarm for above approach
#include <iostream>
#include <cmath>
using namespace std;
 
// Function to convert a number in given base
// to decimal form
int toDecimal(int num, int base) {
    int res = 0, power = 1;
    while (num > 0) {
        int digit = num % 10;
        res += digit * power;
        power *= base;
        num /= 10;
    }
    return res;
}
 
// Function to convert a decimal number
// to given base form
int toBase(int num, int base) {
    int res = 0, power = 1;
    while (num > 0) {
        int digit = num % base;
        res += digit * power;
        power *= 10;
        num /= base;
    }
    return res;
}
 
// Function to find X - Y in base B
int getDifference(int B, int X, int Y)
{
    // Convert X and Y to decimal form
    int X_dec = toDecimal(X, B);
    int Y_dec = toDecimal(Y, B);
 
    // Find the difference in decimal form
    int diff_dec = X_dec - Y_dec;
 
    // Convert the difference to base B form
    int diff = toBase(diff_dec, B);
 
    // Return the difference
    return diff;
}
 
// Driver Code
int main()
{
    int X = 1212;
    int Y = 256;
    int B = 8;
 
    cout << getDifference(B, X, Y);
 
    return 0;
}

Java

//Java code for above approach
import java.lang.Math;
 
public class Main {
    // Function to convert a number in given base
    // to decimal form
    static int toDecimal(int num, int base) {
        int res = 0, power = 1;
        while (num > 0) {
            int digit = num % 10;
            res += digit * power;
            power *= base;
            num /= 10;
        }
        return res;
    }
 
    // Function to convert a decimal number
    // to given base form
    static int toBase(int num, int base) {
        int res = 0, power = 1;
        while (num > 0) {
            int digit = num % base;
            res += digit * power;
            power *= 10;
            num /= base;
        }
        return res;
    }
 
    // Function to find X - Y in base B
    static int getDifference(int B, int X, int Y) {
        // Convert X and Y to decimal form
        int X_dec = toDecimal(X, B);
        int Y_dec = toDecimal(Y, B);
 
        // Find the difference in decimal form
        int diff_dec = X_dec - Y_dec;
 
        // Convert the difference to base B form
        int diff = toBase(diff_dec, B);
 
        // Return the difference
        return diff;
    }
 
    // Driver Code
    public static void main(String[] args) {
        int X = 1212;
        int Y = 256;
        int B = 8;
 
        System.out.println(getDifference(B, X, Y));
    }
}

Output:

Time Complexity: O(log^2 N)
Auxiliary Space: O(log N)

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!