In the positional number system of base `b`, the representation `d_{n}d_{n-1}…d_{1}d_{0}` denotes the number `\sum_{i = 0}^{n} d_i b^i`. For example, the binary (`b = 2`) number `(1001)_2` is 8 + 1 = 9. Notice that when `d_i \in {0, …, b – 1}`, there is only one way to denote any number. This is what we are all used to.
In a redundant number system, we allow `d_i` to be chosen from a larger set of digits. For this series, we will stick to `{0, …, b – 1, b}`. To make things even more concrete, we further set `b` to 2, i.e., we are considering the redundant binary numbers with the sets of digits {0, 1, 2}.
The decimal number 9 can still be written as `1001` in binary (I am dropping the subscripts and will display binary numbers in math mode). But since we are using the redundant binary system, we also have other choices. In particular, `201` (2 * 4 + 1 = 9) and `121` (4 + 2*2 + 1 = 9) are also valid representations.
Let me introduce three terms before I continue.
- We say that a redundant binary number is regular if the 2s and 0s alternate. So `2012` is regular, but `2120` is not.
- When the last non-1 digit of a redundant binary number is 0, we say that it’s 0-exposed. For example, `2001` is 0-exposed. (But note that it is not regular.)
- When the last non-1 digit is 2, we say that it is 2-exposed. For example, `2102` is 2-exposed.
The regularity constraint is very special. First, convince yourself that even when restricting to regular representations, there are still redundancy in the representation of a number. For example, both `1202` and `1210` denote 18 and both of which are regular since the 2s and the 0s alternate.
Also note that if a number is either 2-exposed or 0-exposed.
The only operation that we will consider in this post is:
- add 1 to the least significant digit of a number (i.e., the rightmost)
We will denote this operation with an intuitive expression. For example, consider `12(1+1)`. That would be `122`. Easy, huh?
Let’s repeat the operation one more time. Hmm, `12(2+1)` would be `123`, but that wouldn’t be too good since 3 is not an allowed digit. Well, we need carry. `123` = `131` = `211`. OK, problem solved.
At this point, make sure you know how to do this add-one-to-the-last-digit operation.
For those of us that own the whole series of the Worst-Case Scenario Survival Handbook 
, you will have noticed that this operation can take time linear to the number of digits. Consider the input `22222222222222222(2+1)`. Oh no!
This is where the regularity constraint comes in. Suppose the number you start with is regular. How long can add-1 take? Consider the last digit of the number.
- If it’s a 0 or 1, then you can just bump it up to 1 or 2 respectively.
- If it’s a 2, then we need to carry 1 to the next digit (to the left). Ah! But since the number is regular, that digit cannot be a 2. The previous case now applies.
So in at most two steps, we will be done. That’s like `O(1)` time, right?
But, we may not be left with a regular number any more. For example, `12(1+1)` is `122` and that’s not regular. The key observation is that we will end up with an irregular number if we start with a 2-exposed regular number. So we never want to increment a 2-exposed number.
The claim is that you can convert a 2-exposed number into a 0-exposed equivalent in `O(1)` time if you know where the rightmost 2 is. Let the number be written as `xy2z`, where `z` is the sequence of digits to the right of the rightmost 2, `y` is the digit immediate to the left of it, and `x` is the sequence to the left of `y`. Due to the regularity constraint, note that `z` must be all 1s if it is not null, and `y` only has two possibilities:
- `x02z` = `x10z`
`x` must be 2-exposed, so `x10z` is regular. - `x12z` = `x20z`
`x` must be 0-exposed, so `x20z` is regular.
And both of these are 0-exposed and we know adding 1 to them takes `O(1)` time.
The remaining issue is how we know where the rightmost 2 is. This is easy. We maintain a stack of the locations of the 2s, with the rightmost on the top of the stack. Verify that the above two fixing operations both operate at the top of the stack.
Now do you understand how to add 1 in `O(1)` time?
Indeed, if the number is 2-exposed, fix it to become 0-exposed first. And we know that adding 1 to a 0-exposed number is easy.
But why am I telling you about redundant number systems? That would be the subject of Part 2.
