cf.completefrontend
MATH & GEOMETRY · FOUNDATION

Converting between number bases

Write a number in another base by taking remainders, and read it back by multiplying and adding digit by digit.

Time O(log n)Space O(log n)3 practice problemsStep-through picture

The idea

We write numbers in base 10: the digits of 156 mean 1 × 100 + 5 × 10 + 6 × 1. Each place is worth 10 times the place to its right. Other bases work the same way with a different multiplier. In base 16 (hexadecimal), each place is worth 16 times the one to its right, and the digits go 0-9 then a-f for 10 to 15. In base 2 (binary), the places are worth 1, 2, 4, 8, ....

To write a number in a base, take rest % base: that's the rightmost digit. Then divide rest by the base (rounding down) and repeat to get the next digit to the left. Stop when rest is 0.

To read a number written in a base, go left to right: value = value * base + digit. Each step shifts what you have one place to the left and adds the new digit.

An everyday example

Packing eggs into boxes of boxes

You have 156 eggs. Cartons hold 16 eggs, and crates hold 16 cartons. 156 eggs fill 9 cartons with 12 eggs left over. 9 cartons don't fill a crate. So you have 0 crates, 9 cartons, and 12 loose eggs: in base 16, that's 9c, since c stands for 12. Each step asks "how many are left over after packing into the next size up?"

How the example maps to the code
In the exampleIn the code
Loose eggs left after filling cartonsrest % base
The number of full cartonsMath.floor(rest / base)
Writing the leftover count on the labelout = DIGITS[rest % base] + out
Unpacking: cartons times 16 plus loose eggsvalue = value * base + DIGITS.indexOf(ch)

From the slow way to converting between number bases

  1. Start with the way people often do it by hand: to write 2989 in base 16, find the largest power of 16 that fits (16^2 = 256), count how many times it fits (11 times, the digit b), subtract, and move on to 16^1, then 16^0. It works, but you must first find the right power, and each step divides by a different number.
  2. Notice which digit is easiest to get: the last one. Every place except the last is worth a multiple of the base, so n % base is exactly the last digit. For 2989 % 16 that's 13, the digit d, with no powers needed.
  3. To get the next digit, throw the last one away. Math.floor(n / base) drops the last digit and moves every other digit one place to the right, so the next % base gives the next digit. Repeat until nothing is left. The digits come out from right to left, so each new one goes in front of out.
  4. Reading a number back runs the same idea the other way. Going left to right, value * base shifts what you have one place to the left, and + digit fills the new last place. Handle 0 and the sign before the loop, keep the digit symbols in one DIGITS string, and you have two short loops. Those loops are base conversion.

How it works

  1. Keep the digit symbols in order in a string: DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz".
  2. To write n in base: handle 0 and the sign first, then set rest = Math.abs(n).
  3. While rest > 0, put DIGITS[rest % base] in front of out, then set rest = Math.floor(rest / base).
  4. Return the sign followed by out.
  5. To read text in base: start with value = 0 and, for each character left to right, set value = value * base + DIGITS.indexOf(ch).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. const DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";
  3. function toBase(n, base) {
  4. if (n === 0) return "0";
  5. const sign = n < 0 ? "-" : "";
  6. let rest = Math.abs(n);
  7. let out = "";
  8. while (rest > 0) {
  9. out = DIGITS[rest % base] + out;
  10. rest = Math.floor(rest / base);
  11. }
  12. return sign + out;
  13. }
  15. function fromBase(text, base) {
  16. let value = 0;
  17. for (const ch of text.toLowerCase()) {
  18. value = value * base + DIGITS.indexOf(ch);
  19. }
  20. return value;
  21. }

How fast it is

TimeO(log n)
Extra memoryO(log n)

Each step produces one digit, and n has about log_base n digits. The output string holds those digits.

  • Best caseO(1)

    n is 0, which returns at once, or n is smaller than base, which needs one loop step.

  • Average caseO(log n)

    One step per digit, and n has about log_base n digits: 2989 has 3 digits in base 16.

  • Worst caseO(log n)

    Base 2, which gives the most digits: 2989 needs 12 steps. Adding each digit to the front copies out, but with at most 53 digits that cost stays tiny.

Common mistakes

  • Appending each digit to the end instead of the front. The digits come out from right to left, so the result is reversed.
  • Forgetting 0, which makes the loop return an empty string.
  • Using parseInt without a base, like parseInt("08"). Always pass the base: parseInt(text, 10).
  • Using plain numbers for long hex strings, such as a 20-character ID. Values past 2^53 lose precision; use BigInt("0x" + text) instead.

When to use it

Look for these clues in a problem:

  • The input or output is in hex, binary, octal, or base 36, or uses letters as digits.
  • Colors like #1a2b3c, short IDs, or spreadsheet column names like AB need to become numbers or back.
  • The problem asks for the digits of a number in some base, or for a sum of those digits.
  • Numbers are given as strings because they're too long or use an unusual alphabet.

Check yourself

Answer each one in your head first, then open it.

What does toBase(255, 16) return?

"ff". 255 % 16 = 15, which is f, then rest = 15, and 15 % 16 is also f.

Why must each new digit go in front of out?

The loop finds the last digit first. Adding to the end would build the digits in reverse order: "dab" instead of "bad".

How many loop steps does toBase(2989, 2) take?

12, because 2989 is 101110101101 in binary, which has 12 digits. One step per digit.

Why are fromBase's middle values the same as toBase's rest values in reverse?

Each rest is the number spelled by the digits not yet written out, which are the leading digits. fromBase builds exactly those leading digits, shortest first.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

toBase keeps one promise at the top of every loop: Math.abs(n) equals rest × base^L plus the value of the digits in out, where L is the length of out. At the start out is empty and rest is Math.abs(n), so it's true.

Each step keeps it. Write rest = q × base + r with r = rest % base. Putting the digit for r in front of out and setting rest = q turns (q × base + r) × base^L + out into q × base^(L + 1) + (r × base^L + out), which is the same number. Since r is between 0 and base - 1, it is always a valid single digit.

The loop ends because rest shrinks by a factor of at least base (at least 2) each time, so it hits 0 after one step per digit. Then the promise says Math.abs(n) equals the value of out. fromBase keeps the matching promise: after reading some characters, value is the number those characters spell, because multiplying by base moves every digit one place left and adding the new digit fills the last place.

Going deeper

3 more ideas

Why remainders give the digits from right to left

A number written in base b with digits d2 d1 d0 equals d2 × b² + d1 × b + d0. Every part except d0 is a multiple of b, so n % b is d0, the last digit. Dividing by b and rounding down removes d0 and shifts everything one place right, so the next remainder is d1.

JavaScript's built-ins

(156).toString(16) gives "9c" and parseInt("9c", 16) gives 156, for bases 2 to 36. They're the right choice in real code. Write the loop yourself when the alphabet is unusual (like base 62 with uppercase letters, or spreadsheet columns where A is 1 and there's no zero digit), or when numbers pass 2^53 and need BigInt.

The cost

A number n has about log_base(n) digits, and each loop step produces one, so converting takes O(log n) steps. Reading a string of L characters takes O(L) steps.

Work it by hand

Every step in a table, with why

Write -2989 in base 16, then read the digits back with fromBase.

toBase(-2989, 16), then fromBase("BAD", 16)

Steprest or valueDigitout or chWhat happensWhy
12989-""sign = "-"n isn't 0. It's negative, so sign is "-" and rest becomes Math.abs(-2989) = 2989.
2298913 (d)"d"rest = 1862989 % 16 = 13, the symbol d. 2989 = 186 × 16 + 13, so rest becomes 186.
318610 (a)"ad"rest = 11186 % 16 = 10, the symbol a. It goes in front of d.
41111 (b)"bad"rest = 011 % 16 = 11, the symbol b. Math.floor(11 / 16) is 0.
50-"bad"return "-bad"rest is 0, so every digit is out. The sign goes in front.
60--fromBase startsvalue = 0. text.toLowerCase() turns "BAD" into "bad", so upper and lower case both work.
71111b0 × 16 + 11DIGITS.indexOf("b") is 11.
818610a11 × 16 + 10Shifting 11 one place left gives 176; adding a gives 186.
9298913d186 × 16 + 13Shifting 186 gives 2976; adding d gives 2989. Every character is read.

toBase returns "-bad" and fromBase returns 2989. The values 11, 186, 2989 that fromBase builds are exactly the rest values of toBase, in reverse order.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Converting between number basesO(log n)O(log n)An unusual alphabet, a base above 36, spreadsheet-style columns, or BigInt values.
Built-in toString(base) and parseInt(text, base)O(log n)O(log n)Standard bases from 2 to 36 in real code: they're tested, fast, and short.
Largest power firstO(log n)O(log n)Working by hand, or when digits must come out from left to right as a stream.

Extra memory: O(log n): the output string has one character per digit. Only rest and sign are kept besides it.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Converting between number bases and the other approaches, on a scale where each line up is 10 times more steps.
  • Converting between number bases, Built-in toString(base) and parseInt(text, base), Largest power first O(log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Converting between number bases31020
Built-in toString(base) and parseInt(text, base)31020
Largest power first31020

Inputs that need care

5 tricky inputs
n = 0
The first line returns "0". Without it, the loop wouldn't run and the result would be an empty string.
A negative number: toBase(-2989, 16)
The sign is saved, the digits are computed from Math.abs(n), and the result is "-bad". But fromBase("-bad", 16) returns -1107, because indexOf("-") is -1. Strip the sign before reading.
A character that isn't a digit of the base: fromBase("12z", 10)
z has index 35, so it returns 155 without complaint. Check that every index is from 0 to base - 1, and reject the text otherwise.
A decimal: toBase(3.5, 2)
3.5 % 2 is 1.5, and DIGITS[1.5] is undefined, so it returns "1undefined". The code is for whole numbers only.
A number past 2^53: toBase(2 ** 53 + 1, 16)
The + 1 is lost before the call even starts, so it returns "20000000000000", which is 2^53. Use BigInt for IDs and hashes this large.

Variations and follow-ups

Twists interviewers add

Spreadsheet columns

Column names use A to Z for 1 to 26 and have no zero digit. Subtract 1 before each % 26: n--, then take the letter for n % 26, then n = Math.floor(n / 26). Column 28 is AB, and 703 is AAA.

Your own alphabet

Short links often use base 62 with 0-9, a-z, and A-Z. Only the DIGITS string changes. The loops are the same, and the built-in toString can't do it because it stops at base 36.

BigInt IDs

The same loops work with BigInt values, using rest % 16n and rest / 16n. That's how you convert a 128-bit value, such as a UUID's hex digits, without losing precision.

Collect digits in an array

Instead of adding each digit to the front of a string, push it onto an array and reverse().join("") once at the end. It avoids copying the string on every step, which only matters for very long outputs.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "convert to binary or hex", "spreadsheet column title", "add two binary strings", or any representation where each place is worth a fixed multiple of the next.
  • Explain both directions in one breath: "% base gives the last digit and Math.floor(/ base) removes it, so digits come out right to left. Reading back, value * base + digit adds one digit on the right."
  • Test 0, a negative number, a number smaller than the base, and the largest single digit, like toBase(35, 36), which is "z", against toBase(36, 36), which is "10".
  • The usual follow-up is spreadsheet columns, where there's no zero digit. Explain the n-- before each step, and check it on Z (26) and AA (27).

Where frontend code uses it

The same idea in real UI code
  • CSS hex colors like #1a2b3c are three base-16 numbers: 1a = 26, 2b = 43, 3c = 60. Color pickers convert between hex and rgb() this way.
  • Short IDs and URL shorteners often write a number in base 36 or base 62 so it uses fewer characters. Date.now().toString(36) is a common quick ID.
  • Spreadsheet-like data grids label columns A, B, ..., Z, AA, AB: a base-26 system without a zero digit.

Related algorithms