{"id":10003,"date":"2023-04-28T18:36:56","date_gmt":"2023-04-29T01:36:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10003"},"modified":"2023-04-28T18:37:31","modified_gmt":"2023-04-29T01:37:31","slug":"leetcode-2644-find-the-maximum-divisibility-score","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2644-find-the-maximum-divisibility-score\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2644. Find the Maximum Divisibility Score"},"content":{"rendered":"\n

You are given two 0-indexed<\/strong> integer arrays nums<\/code> and divisors<\/code>.<\/p>\n\n\n\n

The divisibility score<\/strong> of divisors[i]<\/code> is the number of indices j<\/code> such that nums[j]<\/code> is divisible by divisors[i]<\/code>.<\/p>\n\n\n\n

Return the integer<\/em> divisors[i]<\/code> with the maximum divisibility score<\/em>. If there is more than one integer with the maximum score, return the minimum of them.<\/p>\n\n\n\n

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

Input:<\/strong> nums = [4,7,9,3,9], divisors = [5,2,3]\nOutput:<\/strong> 3\nExplanation:<\/strong> The divisibility score for every element in divisors is:\nThe divisibility score of divisors[0] is 0 since no number in nums is divisible by 5.\nThe divisibility score of divisors[1] is 1 since nums[0] is divisible by 2.\nThe divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.\nSince divisors[2] has the maximum divisibility score, we return it.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [20,14,21,10], divisors = [5,7,5]\nOutput:<\/strong> 5\nExplanation:<\/strong> The divisibility score for every element in divisors is:\nThe divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.\nThe divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.\nThe divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.\nSince divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [12], divisors = [10,16]\nOutput:<\/strong> 10\nExplanation:<\/strong> The divisibility score for every element in divisors is:\nThe divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.\nThe divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.\nSince divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length, divisors.length <= 1000<\/code><\/li>
  • 1 <= nums[i], divisors[i] <= 109<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Time complexity: O(m*n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxDivScore(vector& nums, vector& divisors) {\n    int maxScore = 0;\n    int ans = INT_MAX;\n    for (int d : divisors) {\n      int score = 0;\n      for (int x : nums) {\n        score += x % d == 0;\n      }\n      if (score > maxScore) {\n        maxScore = score;\n        ans = d;\n      }\n      if (score == maxScore)\n        ans = min(ans, d);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two 0-indexed integer arrays nums and divisors. The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i]. Return the integer divisors[i] with the maximum divisibility score. If there is more than…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[106,574,177],"class_list":["post-10003","post","type-post","status-publish","format-standard","hentry","category-array","tag-brute-force","tag-divisor","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10003","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=10003"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10003\/revisions"}],"predecessor-version":[{"id":10005,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10003\/revisions\/10005"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10003"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10003"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10003"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}