{"id":7986,"date":"2021-01-17T12:49:07","date_gmt":"2021-01-17T20:49:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7986"},"modified":"2021-01-17T12:57:01","modified_gmt":"2021-01-17T20:57:01","slug":"leetcode-1726-tuple-with-same-product","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1726-tuple-with-same-product\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1726. Tuple with Same Product"},"content":{"rendered":"\n<p>Given an array&nbsp;<code>nums<\/code>&nbsp;of&nbsp;<strong>distinct<\/strong>&nbsp;positive integers, return&nbsp;<em>the number of tuples&nbsp;<\/em><code>(a, b, c, d)<\/code><em>&nbsp;such that&nbsp;<\/em><code>a * b = c * d<\/code><em>&nbsp;where&nbsp;<\/em><code>a<\/code><em>,&nbsp;<\/em><code>b<\/code><em>,&nbsp;<\/em><code>c<\/code><em>, and&nbsp;<\/em><code>d<\/code><em>&nbsp;are elements of&nbsp;<\/em><code>nums<\/code><em>, and&nbsp;<\/em><code>a != b != c != d<\/code><em>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,3,4,6]\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> There are 8 valid tuples:\n(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)\n(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,4,5,10]\n<strong>Output:<\/strong> 16\n<strong>Explanation:<\/strong> There are 16 valids tuples:\n(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)\n(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)\n(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)\n(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,3,4,6,8,12]\n<strong>Output:<\/strong> 40\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,3,5,7]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 10<sup>4<\/sup><\/code><\/li><li>All elements in&nbsp;<code>nums<\/code>&nbsp;are&nbsp;<strong>distinct<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: HashTable<\/strong><\/h2>\n\n\n\n<p>Similar idea to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1-two-sum\/\" data-type=\"post\" data-id=\"903\">\u82b1\u82b1\u9171 LeetCode 1. Two Sum<\/a><\/p>\n\n\n\n<p>Use a hashtable to store all the pair product counts.<\/p>\n\n\n\n<p>Enumerate all possible pairs, increase the answer by the same product counts * 8.<\/p>\n\n\n\n<p>Why time 8? C(4,1) * C(1,1) * C(2,1) * C(1,1)<\/p>\n\n\n\n<p>For pair one AxB, A can be placed at any position in a four tuple, B&#8217;s position is then fixed. For another pair CxD, C has two positions to choose from, D is fixed.<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int tupleSameProduct(vector<int>& nums) {\n    const int n = nums.size();\n    unordered_map<int, int> m;\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < i; ++j)        \n        ans += 8 * m[nums[i] * nums[j]]++;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;nums&nbsp;of&nbsp;distinct&nbsp;positive integers, return&nbsp;the number of tuples&nbsp;(a, b, c, d)&nbsp;such that&nbsp;a * b = c * d&nbsp;where&nbsp;a,&nbsp;b,&nbsp;c, and&nbsp;d&nbsp;are elements of&nbsp;nums, and&nbsp;a != b !=&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,208],"class_list":["post-7986","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-two-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7986","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=7986"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7986\/revisions"}],"predecessor-version":[{"id":7989,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7986\/revisions\/7989"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7986"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7986"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}