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 Bint 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 Codeint 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 approachimport 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 Bdef 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 Codeif __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 approachusing 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 Bfunction 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 Codelet X = 1212;let Y = 256;let B = 8;document.write(getDifference(B, X, Y));// This code is contributed by gfgking</script> |
Output:
734
Time Complexity: O(log10N)
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 formint 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 formint 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 Bint 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 Codeint main(){ int X = 1212; int Y = 256; int B = 8; cout << getDifference(B, X, Y); return 0;} |
Java
//Java code for above approachimport 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:
734
Time Complexity: O(log^2 N)
Auxiliary Space: O(log N)
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!