leetcode Question: Ugly Number II

Ugly Number II

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.

    Analysis:

    This problem needs a little thinking about how to generate the next ugly number.

    From the definition and examples we know that:

    • the ugly number u, must come from a previous ugly number times either 2, 3 or 5, e.g., 8 comes from 4 x 2, where 4 is a ugly number.   
    • the ugly number u[i], may NOT come from u[i-1] x 2, x 3, or x 5, e.g., 10 comes from 2 x 5 (or 5 x 2), but not from its previous ugly number 9.
    So given current ugly number sequence, e.g., 1, 2, 3, we have to figure out which ugly number is used to generate the next ugly number.  It is not hard to find out, the minimum number in [1x2, 1x3, 1x5, 2x2, 2x3, 2x5, 3x2, 3x3, 3x5], but not in current result should be the next ugly number. However, it is not efficient to compute these values every time, and the "not in current result" condition seems annoying .

    Therefore, if we could track the values we compute, it becomes much easier to handle the two issues we mentioned.

    • Maintain 3 lists, each one stores the ugly number times 2, 3, and 5, respectively.
    • Every time, we get the newest ugly number, and update the 3 lists.
    • Keep 3 pointers (say p1, p2, and p3) for the 3 lists, every time just select the min(L1[p1], L2[p2], L3[p3]) as the new ugly number, and update the corresponding pointer.
    • When there are more than one minimum values, remember to update all the corresponding pointers.
    I have draw the following figure, to illustrate the procedure of the method, in which step 1 to step 3 is the first iteration to generate ugly number 2, and step 4 to step 6 is the 2nd iteration to generate ugly number 3.






    Code(C++):

    class Solution {
    public:
        int nthUglyNumber(int n) {
            
            vector<int> l1;
            vector<int> l2;
            vector<int> l3;
            vector<int> res(n, 0);
            l1.push_back(1);
            l2.push_back(1);
            l3.push_back(1);
            res[0] = 1;
            int i1 = 1;
            int i2 = 1;
            int i3 = 1;
           
            for (int i=1;i<n;i++){
                l1.push_back(res[i-1]*2);
                l2.push_back(res[i-1]*3);
                l3.push_back(res[i-1]*5);
                int tmp = min(l1[i1], min(l2[i2],l3[i3]));
                if (tmp == l1[i1]) { res[i] = l1[i1++];}
                if (tmp == l2[i2]) { res[i] = l2[i2++];}
                if (tmp == l3[i3]) { res[i] = l3[i3++];}
            }
            return res[n-1];
        }
    };
    


    Code(Python):

    class Solution(object):
        def nthUglyNumber(self, n):
            """
            :type n: int
            :rtype: int
            """
            l1 = [1]
            l2 = [1]
            l3 = [1]
            res = [0 for x in range(n+1)]
            res[0] = 1
            i1 = 1
            i2 = 1
            i3 = 1
            
            for i in range(n):
                
                l1.append(res[i]*2)
                l2.append(res[i]*3)
                l3.append(res[i]*5)
                tmp = min(min(l1[i1], l2[i2]),l3[i3])
                if tmp == l1[i1]:
                    res[i+1] = l1[i1]
                    i1+=1
                if tmp == l2[i2]:
                    res[i+1] = l2[i2]
                    i2+=1
                if tmp == l3[i3]:
                    res[i+1] = l3[i3]
                    i3+=1
            return res[-2]  
    


    leetcode Question: Ugly Number

    Ugly Number

    Write a program to check whether a given number is an ugly number.
    Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
    Note that 1 is typically treated as an ugly number.

    Analysis:


    The easiest but may be not very optimal solution is just divide the test case by 2, 3, and 5. Finally, the ugly number would return a "1".



    Code(C++):


    class Solution {
    public:
        bool isUgly(int num) {
            if (num<=0){ return false; }
            while (num % 2 == 0){ num = num /2; }
            while (num % 3 == 0){ num = num /3; }
            while (num % 5 == 0){ num = num /5; }
            return num ==1;
        }
    };
    

    Code(Python):


    class Solution(object):
        def isUgly(self, num):
            """
            :type num: int
            :rtype: bool
            """
            if num<=0:
                return False
            while num % 2 == 0:
                num = num /2
            while num % 3 == 0:
                num = num /3
            while num % 5 == 0:
                num = num /5
            return num ==1
    

    leetcode Question: Add Digits

    Add Digits:

    Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
    For example:
    Given num = 38, the process is like: 3 + 8 = 111 + 1 = 2. Since 2 has only one digit, return it.
    Follow up:
    Could you do it without any loop/recursion in O(1) runtime?


    Analysis:


    This is a math problem, which can be easily searched in the web and the only be careful with the python, in which the mod operation always returns positive numbers.


    Code(C++):

    class Solution {
    public:
        int addDigits(int num) {
            return (num-1)%9 +1;
        }
    };
    


    Code(Python):

    class Solution(object):
        def addDigits(self, num):
            """
            :type num: int
            :rtype: int
            """
            if num <= 0:
                return (num -1) % -9 + 1
            else:
                return (num -1) % 9 + 1
    

    leetcode Question: Valid Anagram

    Valid Anagram

    Given two strings s and t, write a function to determine if t is an anagram of s.
    For example,
    s = "anagram", t = "nagaram", return true.
    s = "rat", t = "car", return false.
    Note:
    You may assume the string contains only lowercase alphabets.

    Analysis:


    This simple but important problem would provide you some thinking when dealing with quite a lot of programming questions. The first one is to use sorting, while the other is to use map/hashmap/dictionary.

    Considering this problem, the definition of anagram requires two string have exactly same type of chars and the same count of the chars.

    Therefore, what we need is to compare  the two strings in some ways, so that we can check both the type and the count of the chars in two strings.  Obviously,  find some data structure to save each char would work well. Then it is naturally comes the use of map, which stores the key and value pair in the buffer, and the "check" process takes only O(1) time.  See the code below you will easily find how it works in just several lines of code.

    Using a map will definitely open some new spaces to save the key-value pairs. What if we do not use extra space?  In this problem, if we could "move"  the chars of both strings, check if the two strings are same would solve the anagram. One way of "move" chars is to use sort, since sorting chars is unique to every string and will never lose any of the chars (so the count of chars will not change). So, just sort the strings in same order, then a simple comparison will work well. However, it will take more time, where the sorting have O(n log n) complexity.


    Code(C++):

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            
            int mp[26] = {0};
            if (s.size()!= t.size()){return false;}
            for (int i=0;i<s.size();++i){
                mp[s[i]-'a'] += 1;
                mp[t[i]-'a'] -= 1;
            }
            for (int i=0; i< 26;i++){
                if (mp[i] != 0) {return false;}
            }
            return true;
            
            
            //sort(s.begin(),s.end());
            //sort(t.begin(),t.end());
            //return s == t;
        }
    };
    



    Code(Python):

    class Solution(object):
        def isAnagram(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: bool
            """
            if len(s) != len(t):
                return False
            mp = [0 for x in range(26)]
            for i in range(len(s)):
                mp[ord(s[i])-ord('a')] += 1
                mp[ord(t[i])-ord('a')] -= 1
            for i in range(26):
                if mp[i] != 0:
                    return False
            return True