{"id":9561,"date":"2022-03-08T04:18:45","date_gmt":"2022-03-08T12:18:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9561"},"modified":"2022-03-08T04:19:55","modified_gmt":"2022-03-08T12:19:55","slug":"leetcode-2197-replace-non-coprime-numbers-in-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-2197-replace-non-coprime-numbers-in-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2197. Replace Non-Coprime Numbers in Array"},"content":{"rendered":"\n

You are given an array of integers nums<\/code>. Perform the following steps:<\/p>\n\n\n\n

  1. Find any<\/strong> two adjacent<\/strong> numbers in nums<\/code> that are non-coprime<\/strong>.<\/li>
  2. If no such numbers are found, stop<\/strong> the process.<\/li>
  3. Otherwise, delete the two numbers and replace<\/strong> them with their LCM (Least Common Multiple)<\/strong>.<\/li>
  4. Repeat<\/strong> this process as long as you keep finding two adjacent non-coprime numbers.<\/li><\/ol>\n\n\n\n

    Return the final<\/strong> modified array.<\/em> It can be shown that replacing adjacent non-coprime numbers in any<\/strong> arbitrary order will lead to the same result.<\/p>\n\n\n\n

    The test cases are generated such that the values in the final array are less than or equal<\/strong> to 108<\/sup><\/code>.<\/p>\n\n\n\n

    Two values x<\/code> and y<\/code> are non-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

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

    Input:<\/strong> nums = [6,4,3,2,7,6,2]\nOutput:<\/strong> [12,7,6]\nExplanation:<\/strong> \n- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12<\/u><\/strong>,3,2,7,6,2].\n- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12<\/u><\/strong>,2,7,6,2].\n- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12<\/u><\/strong>,7,6,2].\n- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6<\/strong>].\nThere are no more adjacent non-coprime numbers in nums.\nThus, the final modified array is [12,7,6].\nNote that there are other ways to obtain the same resultant array.\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> nums = [2,2,1,1,3,3,3]\nOutput:<\/strong> [2,1,1,3]\nExplanation:<\/strong> \n- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3<\/strong>,3].\n- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3<\/strong>].\n- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2<\/strong>,1,1,3].\nThere are no more adjacent non-coprime numbers in nums.\nThus, the final modified array is [2,1,1,3].\nNote that there are other ways to obtain the same resultant array.\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 1 <= nums.length <= 105<\/sup><\/code><\/li>
    • 1 <= nums[i] <= 105<\/sup><\/code><\/li>
    • The test cases are generated such that the values in the final array are less than or equal<\/strong> to 108<\/sup><\/code>.<\/li><\/ul>\n\n\n\n
      Solution: Stack<\/strong><\/h2>\n\n\n\n
      “””It can be shown that replacing adjacent non-coprime numbers in any<\/strong> arbitrary order will lead to the same result.”””<\/p>\n\n\n\n
      So that we can do it in one pass from left to right using a stack\/vector.<\/p>\n\n\n\n
      Push the current number onto stack, and merge top two if they are not co-prime.<\/p>\n\n\n\n
      Time complexity: O(nlogm)
      Space complexity: O(n)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector replaceNonCoprimes(vector& nums) {\n    vector ans;\n    for (int x : nums) {\n      ans.push_back(x);\n      while (ans.size() > 1) {\n        const int n1 = ans[ans.size() - 1]; \n        const int n2 = ans[ans.size() - 2]; \n        const int d = gcd(n1, n2);\n        if (d == 1) break;\n        ans.pop_back();\n        ans.pop_back();\n        ans.push_back(n1 \/ d * n2);\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      You are given an array of integers nums. Perform the following steps: Find any two adjacent numbers in nums that are non-coprime. If no such numbers are found, stop the process. Otherwise, delete the two…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[771,359,217,360,180],"class_list":["post-9561","post","type-post","status-publish","format-standard","hentry","category-stack","tag-co-prime","tag-gcd","tag-hard","tag-lcm","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9561","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=9561"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9561\/revisions"}],"predecessor-version":[{"id":9564,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9561\/revisions\/9564"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9561"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9561"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9561"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}