250. Nth 2-3-5 Number

Consider the increasing list of positive integers whose only prime factors are 2, 3 and 5. The number 1 is included and is the first element, so the list begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ... Given n, return the n-th element of this list (counting from 1).

Every element after 1 is obtained by multiplying an earlier element by 2, 3 or 5. Testing each integer in turn to see if it qualifies wastes time on the many integers that do not. Instead build the list in order, using three pointers (one for each multiplier) into the part you have already built, and always append the smallest of the three candidate products.

The answer for the largest n is 2123366400, which fits in a 32-bit signed integer, but candidate products such as 5 times an element can exceed that range temporarily, so use a 64-bit type for them where needed. Time O(n) and space O(n).