Ruby Solution


  • 0
    I

    I passed this problem by reading

    The basic idea is to select the minimum from three lists

    (2) 1×2, 2×2, 3×2, 4×2, 5×2, …
    (3) 1×3, 2×3, 3×3, 4×3, 5×3, …
    (5) 1×5, 2×5, 3×5, 4×5, 5×5, …
    

    It's ingenious to use three pointers to index each list.

      def nth_ugly_number(n)
        numbers = [1]
    
        id2, id3, id5 = 0, 0, 0
    
        (n-1).times do
          candidates = [ 2*numbers[id2], 3*numbers[id3], 5*numbers[id5] ]
          min = candidates.min
    
          id2 += 1 if min == 2*numbers[id2]
          id3 += 1 if min == 3*numbers[id3]
          id5 += 1 if min == 5*numbers[id5]
    
          numbers << min
        end
    
        numbers[n-1]
      end
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.