# Code Puzzle #1 - Solution

If you haven't read the puzzle, you can read more about it on my previous post.

The questions:

- (Answer this first) Take a guess - how many numbers do you think there are between 1 and 1 million that are divisible by their reverse. Any? Fifty? A thousand?
- Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.
- If you use .NET, you may run into a limitation in the framework that's a little surprising.
^{1}What is the limitation?

A few rules:

- We don't count numbers which are palindromes. Of course 42124 is divisible by 42124, but where's the fun in that?
- We don't count numbers which end in 0, since their reverse will drop the zero and that's not what I'm looking for. If we didn't have that rule, we'd have to deal with things like 2000 -> 0002, which only works because we'd drop the leading zeros. Lame.

We had some great feedback and answers in the comments - of course some of the answers were better than mine.

My Solution:

### 1. Take a guess - how many numbers do you think there are between 1 and 1 million that are divisible by their reverse. Any? Fifty? A thousand?

ANSWER: 6

8712 is divisible by 2178

9801 is divisible by 1089

87912 is divisible by 21978

98901 is divisible by 10989

879912 is divisible by 219978

989901 is divisible by 109989In case you're curious, there are 6 more between 1 million and 100 million:

8799912 is divisible by 2199978

9899901 is divisible by 1099989

87128712 is divisible by 21782178

87999912 is divisible by 21999978

98019801 is divisible by 10891089

98999901 is divisible by 10999989

### 2. Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.

Here's my solution; there were some other solutions in the comments that gave the same results.

using System; public class NeverOddOrEven { public static void Main() { for(int i=1;i<1000000;i++) { if(i % 10 != 0) //Ignore numbers which end in 0 { int reversed = int.Parse((ReverseUsingCharArrayInline(i.ToString()))); if(i != reversed && i % reversed == 0) //Ignore palindromes Console.WriteLine("{0} is divisible by {1}", i, reversed); } } Console.WriteLine("Done"); Console.ReadLine(); } //via http://weblogs.asp.net/justin_rogers/archive/2004/06/10/153175.aspx private static string ReverseUsingCharArrayInline(string input) { char[] reversed = new char[input.Length]; for(int i = 0, j = reversed.Length - 1; i <= j; i++, j--) { reversed[i] = input[j]; reversed[j] = input[i]; } return new String(reversed); } }

I'm not sure how to grade this question - I'd say it's a pass / fail, but that's just because some of the solutions were better than mine (grin). Alexander Neumer gave the fastest solution, since it does the reverse function numerically rather than converting to strings:

While n > 0 rev = rev * 10 + (n Mod 10) n = n \ 10 End While

Hmm, I guess I might have tried that if I hadn't made an incorrect assumption about the .NET framework...

### 3. If you use .NET, you may run into a limitation in the framework that's a little surprising. What is the limitation?

I planned to bang this out in a few lines by converting the int to a string, reversing the string, and converting to int:

j=(int)i.ToString().Reverse();

Not blazing fast, but it gets the job done. **That is, it would if the string class had a Reverse() method. Doh!** Justin Rogers had a great comparison of functions which reverse strings a while ago; some of his commenters dug into unsafe code and made it much faster. Mike Mestemaker informed me that VB.NET has a strReverse() function that works well, but Alexander Neumer's solution kept it simple by staying away from strings altogether.

Thanks for playing! We're still waiting on our resident mathematician to explain the interesting patterns in the result; anyone else want to jump in?