class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> m{1};
        int a = 0, b = 0, c = 0;
        while (--n) {
            int t = min(m[a] * 2, min(m[b] * 3, m[c] * 5));
            m.push_back(t);
            if (t == m[a] * 2) {
                ++a;
            }
            if (t == m[b] * 3) {
                ++b;
            }
            if (t == m[c] * 5) {
                ++c;
            }
        }
        return m.back();
    }
};