Monthly Archives: July 2016

Largest Divisible Subset

leetcode 368.

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

Solution is from here. This is actually a DP problem, a sort of like minimum coin problem. Have an array count[] to count the max number of element in subset this an element can belong First, sort the array. Then loop the array in ascending order. For each element right, try to see if any element left is divisible by right: nums[right] % nums[left] == 0,  besides, see if count[left] + 1 > count[right]

So the formula will look like:

count[right] = max{count[right], count[left] + 1 if nums[right] % nums[left] == 0}

In the algorithm, we should still use a parent[] to record where it jumps from.

Check my code on github.

public static List<Integer> largestDivisibleSubset(int[] nums) {
    if (nums.length <= 0) {
        return new ArrayList<Integer>();
    }
    int[] parent = new int[nums.length], count = new int[nums.length];
    Arrays.sort(nums);
    int maxPos = 0; // where the max number in the result subset
    for (int right = 0; right < nums.length; right++) {
        parent[right] = -1;
        count[right] = 1;
        for (int left = 0; left < right; left++) {
            if (nums[right] % nums[left] == 0 && count[left] + 1 > count[right]) {
                parent[right] = left;
                count[right] = count[left] + 1;
                if (count[right] > count[maxPos]) { // update max pos
                    maxPos = right;
                }
            }
        }
    }
    List<Integer> ans = new ArrayList<>();
    while (maxPos != -1) {
        ans.add(nums[maxPos]);
        maxPos = parent[maxPos];
    }
    return ans;
}

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