https://leetcode.com/problems/ugly-number-ii/

Leetcode: 264. Ugly Number II

var cachedUglyNumbers []int

func nthUglyNumber(n int) int {
	if cachedUglyNumbers != nil {
    		// give the desired ugly number
		return cachedUglyNumbers[n-1]
	}

  	// generate all ugly numbers <= MaxInt32, then used cached values for subsequent calls
  
	h := NewIntHeap(1690, 0, false)

  	// generates a list of all powers of a given base from 1 .. MaxInt32
	pN := func(base int) []int {
		ps := []int{}
		for p := 1; p <= math.MaxInt32; p *= base {
			ps = append(ps, p)
		}
		return ps
	}

  	// generate all powers of all ugly primes
	p2s := pN(2)
	p3s := pN(3)
	p5s := pN(5)
  
  	// compute all combinations of ugly factors w/short circuiting 
	for _, p2 := range p2s {
		for _, p3 := range p3s {
			ugly := p2 * p3
			if ugly > math.MaxInt32 {
				break
			}
			for _, p5 := range p5s {
				ugly := ugly * p5
				if ugly > math.MaxInt32 {
					break
				}
        			// maintains an ordered heap
				heap.Push(h, ugly)
			}
		}
	}

  	// convert heap to cache sorted in ascending order
	cachedUglyNumbers = make([]int, h.Len())
	for i := 0;  i < len(cachedUglyNumbers); i++ {
		cachedUglyNumbers[i] = heap.Pop(h).(int)
	}
  
  	// give the desired ugly number
	return cachedUglyNumbers[n-1]
}

// Helper IntHeap

func NewIntHeap(initialSize int, maxSize int, desc bool) *IntHeap {
	return &IntHeap{
		data:    make([]int, initialSize)[0:0],
		desc:    desc,
		maxSize: maxSize,
	}
}

type IntHeap struct {
	data []int
	desc bool // true = descending, false = ascending
	initialSize int
	maxSize int
}

func (h *IntHeap) resetData() {
	h.data = make([]int, h.initialSize)[0:0]
	heap.Init(h)
}

func (h IntHeap) Len() int {
	return len(h.data)
}

func (h IntHeap) Less(i, j int) bool {
	if h.desc {
		return h.data[i] > h.data[j]
	}
	return h.data[i] < h.data[j]
}

func (h IntHeap) Swap(i, j int) {
	h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *IntHeap) Push(x interface{}) {
	h.data = append(h.data, x.(int))
}

func (h *IntHeap) Prune() {
	if h.maxSize == 0 || h.Len() < h.maxSize {
		return
	}
	// pop the desired values
	r := make([]int, h.maxSize)
	for i := 0; i < h.maxSize; i++ {
		r[i] = heap.Pop(h).(int)
	}
	// reset heap data
	h.resetData()
	// push back
	for _, v := range r {
		heap.Push(h, v)
	}
}

func (h *IntHeap) Peek() int {
	return h.data[h.Len()-1]
}

func (h *IntHeap) Pop() interface{} {
	n := h.Len()
	x := h.data[n-1]
	h.data = h.data[0:n-1]
	return x
}