• # Base Conversion

This post will explore an approach to converting a number between different bases, e.g. decimal, hexadecimal, octal, and everything in between. A concrete example might look something like this - (12)10 = (C)16 = (10000)2 with the subscript denoting the base. The general idea is to first convert the number in the given base to decimal, and the second step would be to convert from decimal to the desired base. Suppose we want to convert (913)7 to base 13.

``````# let x = 0
# 9 : 0 * 7 + 9 = 9
# 1 : 9 * 7 + 1 = 64
# 3 : 64 * 7 + 3 = 451

# x = 451 // This is 913 in base 10

# 451 % 13 = 9   451 / 13 = 34 // the new value of x
#  34 % 13 = 8    34 / 13 = 2  // the new value of x
#   2 % 13 = 2     2 / 13 = 0  // the new value of x
# 289 // this is 451 in base 13``````

## Approach

As shown in the illustration, the first step is to convert the given number in the given base to its base 10 counterpart. This is done by iterating through the digits of the given number, starting with the most significant digit, and multiplying the aggregate value by the given base and then adding the digit to the aggregate. Repeat this for the length of the given number. The result will be a base 10 representation of the given number. The key concept to note here is that multiplying by a base effectively moves the digits to the left. This is more obvious with base 10 where multiplying the number 3 by 10 results in 30, which shifts the number 3 to the left by 1.

We can skip to the second step if the given number is already in base 10. This step takes advantage of the property of modulo and the divide operators. The modulo helps pick out the least significant digit while the divide operator reduce a number by the magnitude of the base. This is repeated until the number becomes zero.

## Implementation

``````public static String convert(String givenNumber, int b1, int b2) {
int x = 0;
for (int i = 0; i < givenNumber.length(); i++) {
char c = givenNumber.charAt(i);
x = (x * b1 + (Character.isDigit(c)
? c - '0'
: c - 'A' + 10));
}

StringBuilder sb = new StringBuilder();
while (x > 0) {
int r = x % b2;
char c = (char) (r >= 10
? 'A' + r - 10
: '0' + r);
sb.append(c);
x /= b2;
}

return sb.reverse().toString();
}``````
• ## Get all Paths of BinaryTree

This post continues to explore tree algorithms and specifically printing all root-to-leaf paths when given a binary tree. It will showcase the iterative pre-order depth fir...

• ## Fuel System

One of the most widely known aircrafts in general aviation is the Cessna 172. Depending on the year and model, the aircraft may be equipped with one of the two ways that fu...

Posted by Chau in Aviation.
• ## Rabin Karp Substring Search in Java

This post will explore one of the substring search algorithms known as Rabin-Karp created by Richard M. Karp and Michael O. Rabin. There are two concepts to talk about, the...

• ## Merge Two Sorted Lists

Write an algorithm that merges two sorted lists. The general idea to approach this problem is to have two pointers for the two lists. There will be another pointer to itera...

• ## Determine if BinaryTree is Balanced

This post will explore the problem of checking whether a binary tree is balanced or not. A binary tree is considered to be balanced if the height difference between two sub...

• ## Letter is Constructible from Magazine

The problem in this post is concerned with answering the question of whether a given letter can be reconstructed with a given magazine. The letter is reconstructible when a...

• ## Palindromic Permutation

This post explores the question of if the characters of a given word can rearranged such that the final word is a palindrome. For example, the word "edified" coul...

• ## Convert Roman Numeral to Integer and Vice Versa

This post will explore the situations where there is a need to convert a roman numeral to integer and vice versa. The common basic symbols in the roman numeral system are I...

• ## Palindrome Integer

Given an integer, determine if it is a palindrome number.

### Approaches

There are a couple of methods in approaching this problem. The first thing that comes ...

• ## Lowest Common Ancestor of Two Nodes in a Binary Tree

Any two nodes in a binary tree has the root node as a common ancestor, assuming both nodes are in the same tree. The lower common ancestor node is the furthest node from th...

• ## Singleton Design Pattern

The singleton design pattern is classified as a creational pattern. It is appropriate for scenario where only one copy of the class is needed because singleton enforces tha...

• ## Reverse an Integer

Given an integer, compute and return its reverse form. This problem becomes a regular reversal problem if the integer is converted into a string to get its character array....

• ## Abstract Factory Design Pattern

The Abstract Factory Design Pattern is classified as a creational pattern and is similar to the Factory Design Pattern in a sense that Abstract Factory creates other factor...