Ugly numbers implementation in Ruby

xw19 Published on: 2019-01-27

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

    if 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