Convert decimal to binary, octal or hexa in javascript

A Stack can be used to convert a number from one base to another. Given a number n which we want to convert to base b. Here is the algorithm which we can use to convert a number from decimal to binary, octal or hexadecimal format.

With Stack

Implementation

  • Store the last digit of the n by n % b and push it into the stack.
  • Remove the last digit from n by n / b.
  • Repeat the step 1 and 2 until n becomes 0.
  • Pop the items from the stack and create a converted number string.
function baseConverter(n, b){
 var stack = new Stack();
 var rem, convertedString = '', digits = '0123456789ABCDEF';  
   
 while (n > 0){
  rem = Math.floor(n % b);
  stack.push(rem);
  n = Math.floor(n / b);
 }

 while (!stack.isEmpty()){
   convertedString += digits[stack.pop()];
 }

 return convertedString;
}
Input:
console.log(baseConverter(1021313, 2));
console.log(baseConverter(1021313, 8));
console.log(baseConverter(1021313, 16));

Output:
11111001010110000001
3712601
F9581

Time Complexity: O(log(n)) where n is the no of digits in input number.
Space Complexity: O(no of digits in n).

Time and Space complexity

  • Arithmetic operation like n % b and n / b takes O(1) time and we are reducing n by removing one digit after each operation so it takes O(log(n)) where n is the no of digits in input number.
  • Inserting item in stack takes O(1) time and removing an item from stack also takes O(1) time.
  • We are storing each digit of the n in stack so space complexity is O(n) where n is the no of digits in input number.

Brute force method to convert decimal to binary, octal or hexadecimal

Implementation

  • Store the last digit of the n by n % b and concatenate the previous converted string on its back and store the whole string in converted string.
  • Remove the last digit from n by n / b.
  • Repeat the step 1 and 2 until n becomes 0.
function baseConverter(n, b){
 var rem, convertedString = '', digits = '0123456789ABCDEF';  
   
 while (n > 0){
  rem = Math.floor(n % b);
  convertedString = digits[rem] + convertedString;
  n = Math.floor(n / b);
 }

 return convertedString;
}
Input:
console.log(baseConverter(1021313, 2));
console.log(baseConverter(1021313, 8));
console.log(baseConverter(1021313, 16));

Output:
11111001010110000001
3712601
F9581

Time Complexity: O(log(n)) where n is the no of digits in input number.
Space Complexity: O(1).

Time and Space complexity

  • Arithmetic operation like n % b and n / b takes O(1) time and we are reducing n by removing one digit after each operation so it takes O(log(n)) where n is the no of digits in input number.
  • We are storing the digits in single variable so space complexity is O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *