Code Puzzle #1 - Solution - Jon Galloway

Code Puzzle #1 - Solution

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

The questions:

    1. (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?
    2. Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.
    3. 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:

    1. We don't count numbers which are palindromes. Of course 42124 is divisible by 42124, but where's the fun in that?
    2. 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 109989

In 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?

Published Wednesday, November 8, 2006 11:05 PM by Jon Galloway

Comments

# re: Code Puzzle #1 - Solution

Another interesting property of those numbers is that they all are divisible by 9.

Thursday, November 9, 2006 3:09 AM by Haacked

# re: Code Puzzle #1 - Solution

Just wanted to point out a small 'error' in the otherwise very nice function Reverse(Integer).

Function Reverse(ByVal n As Integer) As Integer

  Dim rev As Integer = 0

  While n > 0

      rev = rev * 10 + (n Mod 10)

      n = n \ 10

  End While

  Return rev

End Function

Try calling the Reverse function with the number 581. the result will not be whats expected.

This is becouse 58 / 10 does not return 5, but instead is rounder up to 6.

One solution is to change the line to:

n = Math.floor(n \ 10)

I liked the puzzle btw :)

Thursday, November 9, 2006 7:58 AM by Mikael Kjellqvist

# re: Code Puzzle #1 - Solution

Fun puzzle!

I had to write it in Ruby, as that's the language I'm trying to gain proficiency in.

It doesn't run fast, but it was fast to code :).

#!/usr/bin/env ruby

class Integer

 def reverse

   r = "#{self}".reverse

   return nil if r =~ /^0/ or r.to_i == self

   return r.to_i

 end

end

biggest = 1000000

(1 .. biggest).each do |n|

 if n.reverse

   puts n if n % n.reverse == 0

 end

end

Friday, November 17, 2006 1:29 AM by Scott Patten

# re: Code Puzzle #1 - Solution

Shouldn't you be getting results like 100 is divisible by 001?

Monday, November 20, 2006 12:03 PM by Helen

# re: Code Puzzle #1 - Solution

@Helen - Take a look at the puzzle rules. I didn't  include them since I don't consider 001 a valid number. I'm sure James Bond might take issue with that.

Monday, November 20, 2006 12:46 PM by Jon Galloway

# a little help please

hi your website is very nice i want a little sorry the solution for this puzzle

"I live in water,if you cut my head iam at your door,if you cut my tail iam a fruit , if you cut both then iam with you"

please send me the solution for this

Sunday, May 6, 2007 1:34 PM by angel

# re: Code Puzzle #1 - Solution

@angel - The answer is a pearl. http://dan.hersam.com/riddles.html

Sunday, May 6, 2007 4:21 PM by Jon Galloway

# re: Code Puzzle #1 - Solution

From the Python command prompt:

>>> for n in xrange(1000000):

... if n%10==0: continue

... r=int(str(n)[::-1])

... if n==r: continue

... if n%r==0: print n

...

8712

9801

87912

98901

879912

989901

>>>

Saturday, September 29, 2007 2:37 AM by Mark Tolonen

# re: Code Puzzle #1 - Solution

@angel  It would be pearl.

Tuesday, March 15, 2011 8:57 AM by Answers Man