952. Calculate the maximum component size according to the common factor: enumerating prime factors + parallel search set application questions

Title Description

This is from LeetCode 952. Calculate the maximum component size by common factor , difficulty is difficulty.

Tag: "Mathematics", "joint search set"

Given a non empty array num composed of different positive integers, consider the following figure:

  • There are num.length nodes, marked from num[0] to num[num.length - 1];
  • Only when nums[i] and nums[j] share a common factor greater than $1$, there is an edge between nums[i] and nums[j].

Returns the size of the largest connected component in the graph.

Example 1:

Input: nums = [4,6,15,35]

Output: 4

Example 2:

Input: nums = [20,50,9,63]

Output: 2

Example 3:

Input: nums = [2,3,6,7,4,12,21,39]

Output: 8

Tips:

  • $1 <= nums.length <= 2 \times 10^4$
  • $1 <= nums[i] <= 10^5$
  • All values in nums are different

Enumerating prime factors + joint search set

First, consider how to use nums to build a graph. The size of nums is $n = 2 \times 10^4$. Enumerate all point pairs and judge whether there is an edge between two numbers. The complexity is $O(n^2\sqrt{M}) $(where $M = 1e5$is the maximum value of $nums[i]$), which does not need to be considered.

Instead of creating a map by "enumerating points + finding common divisors", we can decompose $nums[i]$into prime factors (with a complexity of $O(\sqrt{nums[i]}) $). Assuming that the set of prime factors decomposed is $S$, we can create a map from $S_{k} $to $num[i]$mapping relationship. If $num[i]$and $num[j]$have edges, then $num[i]$and $num[j]$will be mapped by at least the same prime factor.

The number of connected blocks can be maintained by using the "join search set", and the mapping relationship can be maintained by using the "hash table".

When maintaining the mapping relationship, use the prime factor as key and the subscript value $i$as value (we use the subscript $i$as the point number instead of $nums[i]$, which is different from $nums[i]$to narrow the size of the parallel search array from $1e5$to $2 \times 10^4$).

At the same time, when maintaining connected blocks using the "union search set", synchronously maintain each connected block size sz and the current maximum connected block size ans.

Java code:

class Solution {
    static int N = 20010;
    static int[] p = new int[N], sz = new int[N];
    int ans = 1;
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int a, int b) {
        if (find(a) == find(b)) return ;
        sz[find(a)] += sz[find(b)];
        p[find(b)] = p[find(a)];
        ans = Math.max(ans, sz[find(a)]);
    }
    public int largestComponentSize(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int cur = nums[i];
            for (int j = 2; j * j <= cur; j++) {
                if (cur % j == 0) add(map, j, i);
                while (cur % j == 0) cur /= j;
            }
            if (cur > 1) add(map, cur, i);
        }
        for (int i = 0; i <= n; i++) {
            p[i] = i; sz[i] = 1;
        }
        for (int key : map.keySet()) {
            List<Integer> list = map.get(key);
            for (int i = 1; i < list.size(); i++) union(list.get(0), list.get(i));
        }
        return ans;
    }
    void add(Map<Integer, List<Integer>> map, int key, int val) {
        List<Integer> list = map.getOrDefault(key, new ArrayList<>());
        list.add(val);
        map.put(key, list);
    }
}

TypeScript Code:

const N = 20010
const p: number[] = new Array<number>(N), sz = new Array<number>(N)
let ans = 0
function find(x: number): number {
    if (p[x] != x) p[x] = find(p[x])
    return p[x]
}
function union(a: number, b: number): void {
    if (find(a) == find(b)) return 
    sz[find(a)] += sz[find(b)]
    p[find(b)] = p[find(a)]
    ans = Math.max(ans, sz[find(a)])
}
function largestComponentSize(nums: number[]): number {
    const n = nums.length
    const map: Map<number, Array<number>> = new Map<number, Array<number>>()
    for (let i = 0; i < n; i++) {
        let cur = nums[i]
        for (let j = 2; j * j <= cur; j++) {
            if (cur % j == 0) add(map, j, i)
            while (cur % j == 0) cur /= j
        }
        if (cur > 1) add(map, cur, i)
    }
    for (let i = 0; i < n; i++) {
        p[i] = i; sz[i] = 1
    }
    ans = 1
    for (const key of map.keys()) {
        const list = map.get(key)
        for (let i = 1; i < list.length; i++) union(list[0], list[i])
    }
    return ans
};
function add(map: Map<number, Array<number>>, key: number, val: number): void {
    let list = map.get(key)
    if (list == null) list = new Array<number>()
    list.push(val)
    map.set(key, list)
}
  • Time complexity: $O(n\sqrt{M})$
  • Space complexity: $O(n)$

last

This is the No.952 article in our "brush through LeetCode" series. The series began on January 1, 2021. As of the start date, there are 1916 questions on LeetCode, some of which are locked questions. We will finish all the unlocked questions first.

In this series of articles, in addition to explaining the problem-solving ideas, we will also give the most concise code as far as possible. If the general solution is involved, the corresponding code template will also be provided.

In order to facilitate you to debug and submit code on your computer, I have established a relevant warehouse: https://github.com/SharingSou... .

In the warehouse address, you can see the problem solution links of the series of articles, the corresponding codes of the series of articles, the original problem links of LeetCode and other preferred problem solutions.

For more, more comprehensive and popular "written examination / interview" related information, please visit the beautifully arranged Heji new base 🎉🎉

This article is written by mdnice Multi platform Publishing

Tags: Back-end

Posted by patrickrock on Sat, 30 Jul 2022 10:13:45 +0300