Codingame Solution: Balanced ternary computer: encode

Original Problem

Balanced ternary (3 base) is a non-standard positional numeral system. In the standard (unbalanced) ternary system, digits have values 0, 1 and 2. The digits in the balanced ternary system have values −1, 0, and 1. We use letter T to represent -1, so the digits are (T, 0, 1).

E.g.: \(1T0 = 1 \cdot 3^2 + (-1)\cdot 3^1 + 0\cdot 3^0 = 9 - 3 + 0 = 6\)

You must convert input integer (decimal) number to its balanced ternary representation.

Input
Line 1 An integer (decimal) number N

Output
Line 1 A balanced ternary number BT as string matching the input.

Constraints
\(-30 000 < N < 30 000\)

Solution

In order to convert a number in base ten to a balanced ternary representation, we first convert the number to an ordinary base-three representation and then convert it to a balanced ternary. Handling negative numbers needs a careful handling as well.

The first step to convert a base ten number to another base is trivial, simply divide by the base, take the integer remainder as a digit in the new representation and continue the procedure with the integer quotient.

do {
  digit = n % 3;
  n = n / 3 | 0;
} while (n > 0)

Now to the interesting part, on how to convert a base-3 value to a balanced ternary value. When we take the number 0, the result is also \(0\cdot 3^0=0\). For 1 it is the same with \(1\cdot 3^0=1\). For 2 it is getting interesting, with \(1\cdot 3^1 + (-1)\cdot 3^0=1T\), whereby the base-3 representation of 2 is also 2.

The algorithm is as follows: We first reverse the order of the base-3 representation. Since we want to change the scale, we add one to all 2 digits. Since we have a carry-over this way, we need to add one to the next position. The whole thing must be done in reverse order, so the least significant bit is on the left and we add from left to right!

When we have a negative number in base 10, we can work as if the number were positive, but have to swap 1 with T and T with 1, or in other words: We multiply it by T.

When trying to minimize the algorithm as much as possible, the following comes out:

let n = +readline();
let s = "";

do {
  // Handle negative digits correctly
  let r = (n + 30000) % 3;
  // Handle carry
  n-= [0, 1, -1][r];
  // Divide for base change
  n = n / 3 | 0;
  // Select the correct digit and add in reverse order
  s = "01T"[r] + s;
} while (n != 0);

print(s);