{"id":8139,"date":"2021-02-20T22:16:18","date_gmt":"2021-02-21T06:16:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8139"},"modified":"2021-02-20T22:34:48","modified_gmt":"2021-02-21T06:34:48","slug":"leetcode-1766-tree-of-coprimes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1766-tree-of-coprimes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1766. Tree of Coprimes"},"content":{"rendered":"\n

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n<\/code> nodes numbered from 0<\/code> to n - 1<\/code> and exactly n - 1<\/code> edges. Each node has a value associated with it, and the root<\/strong> of the tree is node 0<\/code>.<\/p>\n\n\n\n

To represent this tree, you are given an integer array nums<\/code> and a 2D array edges<\/code>. Each nums[i]<\/code> represents the ith<\/sup><\/code> node’s value, and each edges[j] = [uj<\/sub>, vj<\/sub>]<\/code> represents an edge between nodes uj<\/sub><\/code> and vj<\/sub><\/code> in the tree.<\/p>\n\n\n\n

Two values x<\/code> and y<\/code> are coprime<\/strong> if gcd(x, y) == 1<\/code> where gcd(x, y)<\/code> is the greatest common divisor<\/strong> of x<\/code> and y<\/code>.<\/p>\n\n\n\n

An ancestor of a node i<\/code> is any other node on the shortest path from node i<\/code> to the root<\/strong>. A node is not <\/strong>considered an ancestor of itself.<\/p>\n\n\n\n

Return an array <\/em>ans<\/code> of size <\/em>n<\/code>, where <\/em>ans[i]<\/code> is the closest ancestor to node <\/em>i<\/code> such that <\/em>nums[i]<\/code> and <\/em>nums[ans[i]]<\/code> are coprime<\/strong>, or -1<\/code> if there is no such ancestor<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]\nOutput:<\/strong> [-1,0,0,1]\nExplanation:<\/strong> In the above figure, each node's value is in parentheses.\n- Node 0 has no coprime ancestors.\n- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).\n- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's\n  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.\n- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its\n  closest valid ancestor.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]\nOutput:<\/strong> [-1,0,-1,0,0,0,-1]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • nums.length == n<\/code><\/li>
  • 1 <= nums[i] <= 50<\/code><\/li>
  • 1 <= n <= 105<\/sup><\/code><\/li>
  • edges.length == n - 1<\/code><\/li>
  • edges[j].length == 2<\/code><\/li>
  • 0 <= uj<\/sub>, vj<\/sub> < n<\/code><\/li>
  • uj<\/sub> != vj<\/sub><\/code><\/li><\/ul>\n\n\n\n
    Solution: DFS + Stack<\/strong><\/h2>\n\n\n\n
    Pre-compute for coprimes for each number.<\/p>\n\n\n\n
    For each node, enumerate all it’s coprime numbers, find the deepest occurrence. <\/p>\n\n\n\n
    Time complexity: O(n * max(nums))
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector getCoprimes(vector& nums, vector>& edges) {\n    constexpr int kMax = 50;\n    const int n = nums.size();\n    vector> g(n);\n    for (const auto& e : edges) {\n      g[e[0]].push_back(e[1]);\n      g[e[1]].push_back(e[0]);\n    }    \n        \n    vector> coprime(kMax + 1);\n    for (int i = 1; i <= kMax; ++i)\n      for (int j = 1; j <= kMax; ++j)\n        if (gcd(i, j) == 1) coprime[i].push_back(j);\n    \n    vector ans(n, INT_MAX);\n    vector>> p(kMax + 1);\n    function dfs = [&](int cur, int d) {    \n      int max_d = -1;\n      int ancestor = -1;\n      for (int co : coprime[nums[cur]])\n        if (!p[co].empty() && p[co].back().first > max_d) {\n          max_d = p[co].back().first;\n          ancestor = p[co].back().second;          \n        }\n      ans[cur] = ancestor;\n      p[nums[cur]].emplace_back(d, cur);\n      for (int nxt : g[cur])\n        if (ans[nxt] == INT_MAX) dfs(nxt, d + 1);\n      p[nums[cur]].pop_back();\n    };\n    \n    dfs(0, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n – 1 and exactly n – 1 edges. Each node has a…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[638,33,217,28],"class_list":["post-8139","post","type-post","status-publish","format-standard","hentry","category-searching","tag-ancestor","tag-dfs","tag-hard","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8139","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8139"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8139\/revisions"}],"predecessor-version":[{"id":8141,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8139\/revisions\/8141"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}