Ugly numbers are natural numbers whose prime factors consists of 2,3 and 5 only. Here is my implemetation using Dynamic programming.

def MIN(a, b, c)
    min = c
    if (a < b && a < c)
        min = a
    elsif b < c
        min = b
    end
    min
end

def next_ugly_number(a)
    ugly = []
    ugly[0] = 1
    i2 = i3 = i5 = 0
    next_multiple_of_2 = ugly[i2] * 2
    next_multiple_of_3 = ugly[i2] * 3
    next_multiple_of_5 = ugly[i2] * 5

    next_ugly_no = ugly[0]

    1.upto(a-1) do |i|
        next_ugly_no = MIN(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly[i] =  next_ugly_no
        if next_ugly_no == next_multiple_of_2
          i2  = i2 + 1
          next_multiple_of_2 = ugly[i2] * 2
        end

        if next_ugly_no == next_multiple_of_3
            i3  = i3 + 1
            next_multiple_of_3 = ugly[i3] * 3
        end

        f next_ugly_no == next_multiple_of_5
      i5  = i5 + 1
      next_multiple_of_5 = ugly[i3] * 5
    end
  end
  next_ugly_no
end

p next_ugly_number(10)
=> 12

Leave a Reply

Your email address will not be published. Required fields are marked *