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).