Daily Archives: July 1, 2016

Sum of Two Integer

leetcode 371. Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Soltuion is from here. Each time, we use xor to calculate current sum, and to calculate current carrier. Loop this until carrier is zero.

public static int getSum(int a, int b) {
    /*
    sum = a ^ b
    carrier = (a & b) << 1
     */
    while (b != 0) {
        int sum = a ^ b;    // to get the current sum
        b = (a & b) << 1;   // to get the carrier
        a = sum;
    }
    return a;
}

Check my code on github: link

Minimum Height Trees

leetcode 310. For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Solution. The solution is easy. Delete the leaves in each round until there are 1 or 2 nodes. That nodes will be the result.

2 things are worth to notice:

1. Because tree nodes are marked by 0, 1, 2, 3, 4 … Consider constructing tree in ArrayList<HashSet<Integer>>, instead of HashMap<Integer, HashSet<Integer>>

2. Maintain a leave set, each time remove the leaves. Then update leave. Once the tree is built, this process takes O(V) time, which V is the number of nodes.

Check my code on github: link