online advertising

Thursday, August 20, 2015

LeetCode OJ - Ugly Number II

Problem:

Please find the problem here.

Solution:

Think of this problem as a variant for BFS. We start with node 1 and explore all the ugly numbers. Every node branch off to its product with 2, 3, 5. That yields an infinite tree of all ugly numbers.

But wait, this tree will have duplicates. For example, node 2 branch of to 6, and node 3 also branch off to 6. To solve this problem, we need to make sure the sub-trees never overlap. In particular, the subtree of 3 will never contain an ugly number having a factor of 2, and the subtree of 5 will never have a factor of 2 or 3.

So when we expand, we need to know if its comes from which subtree. (we will see how to solve this soon)

Next, even if we have the tree, we need to be able to walk the tree in numeric order. To do this, it seems that we will need a queue that give us the smallest number. That is not easy, one could use a priority queue, but here we devise a simpler plan.

Have 3 queues, queues of 2, queues of 3 and queues of 5.

By the time we visit the numbers, it is in numeric order, so if we enqueue the number multiply by 2 in queues of 2, and so on, we can be sure that the queues themselves are in numeric order. So when we dequeue, just compare the heads and we are good to go.

We have also just solved the from which subtree problem!

Code:

#include "stdafx.h"

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

#include "LEET_UGLY_NUMBER_II.h"
#include <queue>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_UGLY_NUMBER_II
{
    typedef long long int64;

    class Solution
    {
    public:
        int nthUglyNumber(int n)
        {
            if (n == 1)
            {
                return 1;
            }
            int count = 1;
            queue<int64> queue2;
            queue<int64> queue3;
            queue<int64> queue5;
            queue2.push(2);
            queue3.push(3);
            queue5.push(5);
            int64 currentUglyNumber = 1;
            while (count < n)
            {
                int64 front2 = queue2.front();
                int64 front3 = queue3.front();
                int64 front5 = queue5.front();

                if (front2 < front3 && front2 < front5)
                {
                    currentUglyNumber = front2;
                    queue2.pop();
                    queue2.push(currentUglyNumber * 2);
                    queue3.push(currentUglyNumber * 3);
                    queue5.push(currentUglyNumber * 5);
                    count++;
                }
                else if (front3 < front2 && front3 < front5)
                {
                    currentUglyNumber = front3;
                    queue3.pop();
                    queue3.push(currentUglyNumber * 3);
                    queue5.push(currentUglyNumber * 5);
                    count++;
                }
                else if (front5 < front2 && front5 < front3)
                {
                    currentUglyNumber = front5;
                    queue5.pop();
                    queue5.push(currentUglyNumber * 5);
                    count++;
                }
            }

            return (int)currentUglyNumber;
        }
    };
};

using namespace _LEET_UGLY_NUMBER_II;

int LEET_UGLY_NUMBER_II()
{
    Solution s;
    cout << (s.nthUglyNumber(1600) == 1399680000) << endl;
    
    return 0;
}

No comments :

Post a Comment