O(n) Java solution


  • 167
    S

    The idea of this solution is from this page:http://www.geeksforgeeks.org/ugly-numbers/

    The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
    because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:

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

    We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5.

    Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

    Every step we choose the smallest one, and move one step after,including nums with same value.

    Thanks for this author about this brilliant idea. Here is my java solution

    public class Solution {
        public int nthUglyNumber(int n) {
            int[] ugly = new int[n];
            ugly[0] = 1;
            int index2 = 0, index3 = 0, index5 = 0;
            int factor2 = 2, factor3 = 3, factor5 = 5;
            for(int i=1;i<n;i++){
                int min = Math.min(Math.min(factor2,factor3),factor5);
                ugly[i] = min;
                if(factor2 == min)
                    factor2 = 2*ugly[++index2];
                if(factor3 == min)
                    factor3 = 3*ugly[++index3];
                if(factor5 == min)
                    factor5 = 5*ugly[++index5];
            }
            return ugly[n-1];
        }
    }

  • 1
    L

    This idea is amazing!
    Thanks for sharing!


  • 5
    F

    Thanks for sharing. I think the key here is as you mentioned, "including nums with same value.". factor2 and factor3 may both have value = 6, but we bump both "6"s together, thus the duplicated 6 won't cause any problem. I initially put it as "else if (factor3==min)", that fell to the trap :)


  • 0
    Y
    This post is deleted!

  • 3
    F

    Your code is very concise.
    I just modified it a little bit.

    Since java program can keep some static members,
    we can calculate all the ugly numbers that are less than or equal to Integer.MAX_VALUE and just store the result into a static array. After some trial, I found that, it is enough to get an array that have 1691 elements. (the 1691st ugly number is 2125764000 while the 1692nd one is 2147483648 which just overflow).

    So for example, if we are asked what is the 1691st, 1690th, 1689th, 1688th, 1687th, .... ugly number, we will not need to calculate what we already know~ Just one round of calculation and all we need to do is to return the queried element in the array.

    public class Solution {
        static int[] ugly = new int[1691];
        static {
            ugly[0] = 1;
            int index2 = 0, index3 = 0, index5 = 0;
            int factor2 = 2, factor3 = 3, factor5 = 5;
            for (int i = 1; i < ugly.length; i++) {
                int min = Math.min(Math.min(factor2, factor3), factor5);
                ugly[i] = min;
                if (factor2 == min)
                    factor2 = 2 * ugly[++index2];
                if (factor3 == min)
                    factor3 = 3 * ugly[++index3];
                if (factor5 == min)
                    factor5 = 5 * ugly[++index5];
            }
        }
    
        public int nthUglyNumber(int n) {
            return ugly[n - 1];
        }
    }

  • 1
    S

    What if I only want the fifth ugly bum, however you calculate all 1691ugly nums. It might be useful under some specific conditions. But I think we should focus on algorithm here.


  • 0
    F

    Yes, if we are asked what the 5th ugly number is, a lot of calculation is wasted.
    But generally speaking, the test cases will be large enough.
    By the way, I agree with you, the algorithm is the most important thing here.


  • 0
    C

    Why other guys give you so many down votes, I don't know why, it's a tragedy!


  • 0
    Y
    This post is deleted!

  • 0
    C

    Nice solution, it's very clever to find out every subsequence is ugly sequence itself multiply by 2, 3, 5.


  • 0
    X

    I feel confused too


  • 0
    W

    maybe something we did not seen has been edited


  • 0
    W

    what happened to this post?


  • 0
    L

    i just write to thanks the person who made the post maybe others assume this should be an answer lol


  • 0
    W

    pat pat poor guy~~~~


  • 0
    T

    lmao can we rollback to the checkpoint before you edited the comment.


  • 0

    It's not edited. lol. Thank You posts should usually be under comments. :P


  • 4
    S

    Here is an more concise version:

    public int nthUglyNumber(int n) {
            int[] nums = new int[n];
            int index2 = 0, index3 = 0, index5 = 0;
            nums[0] = 1;
            for(int i = 1; i < nums.length; i++){
                nums[i] = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
                if(nums[i] == nums[index2] * 2)
                    index2++;
                if(nums[i] == nums[index3] * 3)
                    index3++;
                if(nums[i] == nums[index5] * 5)
                    index5++;
            }
            return nums[n - 1];
        }
    

  • 0
    R

    Golang solution:

    func nthUglyNumber(n int) int {
        ugly:= make([]int, n)
        for k,_ := range ugly {
            ugly[k] = 0
        }
            ugly[0] = 1;
            index2, index3, index5 := 0, 0, 0
            factor2, factor3, factor5 := 2, 3, 5
            for i:=1;i<n;i++ {
                min := min(min(factor2,factor3),factor5)
                ugly[i] = min;
                if factor2 == min {
                    index2++
                    factor2 = 2*ugly[index2]
                }
                if factor3 == min {
                    index3++
                    factor3 = 3*ugly[index3]
                }
                if factor5 == min {
                    index5++
                    factor5 = 5*ugly[index5]
                }
            }
            return ugly[n-1]
    }
    
    func min (a int, b int) int {
        if a > b {
            return b
        } else {
            return a
        }
    }
    

  • 0
    L

    I don't know why the result of merging sequence(1), sequence(2) and (3) is euqal to ugly numbers set?


Log in to reply
 

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