Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### ebanner's blog

By ebanner, history, 8 months ago, ,

Let's consider the problem of converting a number to base k. Initially I was confused by this algorithm, but the more I think about it the more it makes sense.

The algorithm is this. For a number n in base 10, if we wish to convert n to base k then we do the following.

digits = []
while n > 0:
digit = n%k
digits.append(digit)
n /= k
n_k = reversed(digits)


where n_k is the number n in base k.

Why does this work? Well the first thing to notice is that for any natural number base k we can write a number n in base 10 in the following way.

n = sum of i from 0 to infinity of c_i*(k^i)


where 0 <= c_i < k. ***

As a concrete example consider writing 11 in base 3. By the above declaration we can write the following.

11 = 1*3^2 + 0*3^1 + 2*3^0


Now why is this useful? Well if you read off the coefficients from left to right of the above expression, that is 11 in base 3!

11_10 = 102_3


where n_k is the number n in base k.

So given this fact, we just need a way to read off the coefficients of each of these terms. Here is an algorithm for doing so.

1. Read off the rightmost coefficient
2. Shift all the terms rightwards while eliminating the rightmost term
3. Go back to step 1

We can accomplish step 1 by doing n % k.

11 % 3 = (1*3^2 + (0*3)^1 + 2*3^0) % 3
= 0      + 0       + 2


To see why this is the case note that all the terms except the rightmost term have a modulus of zero (because they contain at least one factor of 3). So doing the modulus has the effect of reading off the rightmost coefficient.

Now how do we do step 2? We just do n / k. Let's look and see what that does.

10 / 3 = [1*3^2      +  0*3^1     + 2*3^0] / 3
= (1*3^2)/3   + (0*3^1)/3  + (2*3^0)/3
= 1*(3^1)     +  0*3^0     + 0
= 1*(3^1)     +  0*3^0


Notice the last term zeros out because there is no factor of 3.

So it looks like we've done the main things required to convert to base k. As a last (and small) order of business notice that we've accumulated digits from right to left and hence they are backwards. We only need to reverse them to straighten them out.

*** A proof of this fact is outside the scope of this guide (I'm sure there is a proof out there somewhere). To convince you that this is true, consider that if it was not true then we wouldn't be able to use binary nor octal nor hexadecimal to represent numbers (why?).

•
• -16
•

 » 8 months ago, # |   0 Auto comment: topic has been updated by ebanner (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 2 →   0 Sorry bro. No time for this tutorial. If conversion of base is needed, I will just use a Java one-liner. See https://stackoverflow.com/questions/15735079/convert-from-one-base-to-another-in-java
•  » » 8 months ago, # ^ |   0 The point of this blog post is to show how base conversion is done, so if you need to modify the algorithm to solve in a problem you will be in a position to do so.I noticed all blog posts similar to this one receive lots of downvotes. Can you help me understand why?Is it the length? The fact it's python? No pictures? Not specifically targeting a problem?