Sunday, August 22, 2010

Project Euler : Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

Problem 52
It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.


Solution(in Ruby)

The solution to this problem is simple and straight forward as shown below. Just convert the problem statement into code with tweaks here and there, we should arrive at the solution smoothly. Do not get scared by the catch statement, its just to break nested loops. Moreover, it is enough to inspect numbers that start with 1. The obvious reason being numbers that begin with 2 get more digits when multiplied by 6 which would defeat our purpose.

INFINITY = 1.0 / 0.0
catch (:done) do
  1.upto(INFINITY) do |i|
    ((10**i)...(2*10**i)).each do |x|
      y = x.to_s.split(//)
      if ( y - (x*2).to_s.split(//) ).size == 0 && y.size == (x*2).to_s.split(//).size &&
         ( y - (x*3).to_s.split(//) ).size == 0 && y.size == (x*3).to_s.split(//).size &&
         ( y - (x*4).to_s.split(//) ).size == 0 && y.size == (x*4).to_s.split(//).size &&
         ( y - (x*5).to_s.split(//) ).size == 0 && y.size == (x*5).to_s.split(//).size &&
         ( y - (x*6).to_s.split(//) ).size == 0 && y.size == (x*6).to_s.split(//).size
        puts "The minimum unique number is #{x}"
        throw :done
      end
    end
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh

No comments: