A tough question

[Jim Little]

Tunesters,

I've got a problem that you might be interested in.  I think I've solved
it, but I think it's a fairly common problem, so you might know a better
way or see a flaw in my reasoning.  Besides, it's a fun challenge.

The challenge is to create an algorithm:

input: a string of decimal digits representing an integer
outputs: a string of binary digits representing the same integer
example: Given '42', return '101010'.

The catch: The input string can be arbitrary length.  So you can't just
convert the string to a 32-bit (or 64-bit, or 128-bit, etc) integer and
read off the bits.

I think I've got a solution which is O(n) for memory and O(n log n) for
CPU.  Here it is: (stop reading now if you want to try to solve it
yourself)

Tril: You never really explained your 'shift' technique.  I'd like to
hear about that if you don't mind.



[spoiler space]



















The key is to use the standard algorithm for converting decimal to
binary, but to make it operate as a string algorithm, not as a numeric
algorithm.  So here it is:

0. Start with empty output string.
1. Look at the right-most character in the input string.
2. If it is in {1, 3, 5, 7, 9}:
   2a2. Add a '1' to the front of the output string.
   2a1. Convert 1->0, 3->2, 5->4, 7->6, 9->8.
Else it is in {0, 2, 4, 6, 8}:
   2b1. Add a '0' to the front of the output string.
3. Perform "Divide" algorithm on input string.
5. If input string is '0', stop.  Else go to step 1.

The "Divide" algorithm:
Constraint: The right-most character of the string must be in {0, 2, 4,
6, 8}.

1. Look at the right-most character of the string.
2. If it is in {0, 2, 4, 6, 8}:
   2a1. Convert 0->0, 2->1, 4->2, 6->3, 8->4.
Else it is in {1, 3, 5, 7, 9}:
   2b1. Convert 1->0, 3->1, 5->3, 7->5, 9->7.
   2b2. Convert next character to right: 4->9, 3->8, 2->7, 1->6, 0->5.
3. Look at next character to the left.
4. If there is such a character, go to step 2.  Else stop.

Jim