[Leetcode] Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Analysis:

As we know, n! = n * (n-1) * (n-2) * ... * 2 * 1. A simple way to get the trailing zeros is to calculate the value of n! and then count the trailing zeros. The problem is that the value of n! is too big to be hold by an integer. Even if we express the  n! using string, its time complexity is O(N), which does not satisfy the "logarithmic time complexity". 

Observed that every pair factor 5 and 2 of the number 1 to n will contribute a trailing zero for n!. Since from 1 to n, the number of  factor 2 is always greater than the factor of 5, the number of factor 5 is the number of trailing zeros. 

So the problem becomes how many of factor 5 among the number 1 to n. We know there are n/5 factor 5 from 1 to n (named 5, 10, 15, ...., floor(n/5) * 5) and there are n/25 extra factor of 5 (named 25, 50, 75, ... , floor(n/25)*25), and n/125 extra factor of 5, and so on. It is not so difficult to implement the code and the following code explains itself. One special case to handle is the k may be exceed the INT_MAX so better to use long to avoid overflow. 

    

    int trailingZeroes(int n) {
        int count = 0;
        long k = 5;
        while(n >= k)
        {
            count+=n/k;
            k*=5;
        }
        return count;
    }

[Leetcode] Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:

An element m appearing more than n/2 times in the array means that the number of elements which is equal to m is greater than the ones which are different than m. So, if we increment the number by 1 for the m and decrement the number by for other different element, the element left which has count greater than 1 will be the majority element m. 

The code is very strait forward if you got the idea. The time complexity is O(n) since only one loop is needed. Pretty awesome, isn't it?

  int majorityElement(vector<int> &num) {
        int count = 0;
        int m;
        for(int i=0; i < num.size();i++)
        {
            if (count == 0)
            {
                m = num[i];
                count++;
            }
            else 
            {
                if (m != num[i])
                {
                    count--;
                }
                else
                {
                    count++;
                }
            }
        }
        return m;
    }

[Leetcode] Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Analysis:

An intuitive way to solve the problem is to sort the numbers by some order and then combine the numbers together by descending order.
The question is how should we sort the number? Apparently, it should not be sorted by the integer value. Given two numbers, how do we know which one is "bigger" in term of the combination results is bigger? It is pretty strait forward, just get the two string combinations and compare which one is bigger. For example, [12, 121], since 12121 is greater than 12112, 12121 is the number we want.
The code is pretty strait forward except don't forget to handle the special case of [0, 0], the result should be "0"  rather then "00" as there is no number of "00". 

    static int myComp(int num1, int num2)
    {
        string s1 = to_string(num1) + to_string(num2);
        string s2 = to_string(num2) + to_string(num1);
        return s1 < s2;
    }

    string largestNumber(vector &num) {
        sort(num.begin(), num.end(), myComp);
        //for case [0, 0], if max is 0, then return "0" rather than "00"
        if (num[num.size()-1] == 0)
            return "0";
        string s;
        for(int i=num.size()-1; i>=0; i--)
            s.append(to_string(num[i]));
            
        return s;
    }

[Leetcode] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

The idea is pretty straightforward: count the length of list A and B, and move the longer list few steps from its head so that two list are at the same position to the end of the list. Move both lists toward the end of the lists and whenever they met, the node is the first node the intersection begins.

     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = 0;
        ListNode* p1 = headA;
        while(p1 != NULL) {
            l1++;
            p1 = p1->next;
        }
        
        int l2= 0;
        ListNode* p2 = headB;
        while(p2 != NULL) {
            l2++;
            p2 = p2->next;
        }
        
        p1 = headA;
        p2 = headB;
        if (l1 > l2) {
            for(int i=0; i<l1-l2; i++)
                p1 = p1->next;
        }
        else {
            for(int i=0; i<l2-l1; i++)
                p2 = p2->next;            
        }
        
        while(p1 != NULL && p2 != NULL && p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
            
        return p1;
    }

[Leetcode] Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Analysis:

Similar to Find Minimum in Rotated Sorted Array, except that you need to take care of duplicate one.

int findMin(vector &num) {
        int b = 0;
        int e = num.size()-1;
        int minVal = num[0];
        while(b <= e)
        {
            int m = (b+e)/2;
            if (num[m] > num[b])
            {
                minVal = min(minVal, num[b]);
                b = m + 1;
            }
            else if (num[m] < num[e])
            {
                minVal = min(minVal, num[m]);
                e = m - 1;
            }
            else if (num[m] == num[e])
            {
                minVal = min(minVal, num[m]);
                e--;
            }
            else if (num[m] == num[b])
            {
                minVal = min(minVal, num[m]);
                b++;
            }
        }
        return minVal;        
    }

[Leetcode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis:

Since it is sorted array, binary search may be the hint. Let m be the middle index of array num, if num[0] < num[m], then first part is sorted, the minimum element would be either num[0] or the minimum of the second part, which can be computed recursively. Similarly, if num[m] < num[n], second part is sorted, the minimum element would be either num[m] or the minimum of the first part. 

 int findMin(vector<int> &num) {
        int b = 0;
        int e = num.size() - 1;
        int minValue = INT_MAX;
        while(b <= e) {
            int m = b + (e- b)/2;
            //it is sorted from b to m
            if (num[b] <= num[m]) {
                minValue = min(num[b], minValue);
                b = m + 1;
            }
            else {
                minValue = min(num[m], minValue);
                e = m-1;
            }
        }
        return minValue;
    }

[Leetcode] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Analysis:

Apparently, we need to use extra space to store the minimum element of the stack. We can use one stack s to store the pushed element and another stack sMin to store minimum elements appearing so far. Whenever an element x is pushed, if it is less than current minimum (at the top of sMin stack), push x to the sMin; otherwise, the top of the sMin is the minimum and we push it to sMin;

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x < sMin.top())
            sMin.push(x);
        else
            sMin.push(sMin.top());
    }

    void pop() {
        s.pop();
        sMin.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

However, it could not pass Leetcode oj as Memory Limit Exceeded.  By looking at the solution again, we notice that if x is greater than minimum value, there is no need to push the sMin top value. Just do some special handle when popping the element: if the element is greater than minimum, do not pop sMin.

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x <= sMin.top())
            sMin.push(x);
    }

    void pop() {
        if (s.top() <= sMin.top())
            sMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

In addition, we notice that if all the pushed elements are the same, there are still spaces wasted. It is possible to have a better solution so that few spaces needed for sMin.