{"id":7253,"date":"2020-08-15T22:48:24","date_gmt":"2020-08-16T05:48:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7253"},"modified":"2020-08-15T22:50:36","modified_gmt":"2020-08-16T05:50:36","slug":"leetcode-1552-magnetic-force-between-two-balls","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1552-magnetic-force-between-two-balls\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1552. Magnetic Force Between Two Balls"},"content":{"rendered":"\n

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n<\/code> empty baskets, the ith<\/sup><\/code> basket is at position[i]<\/code>, Morty has m<\/code> balls and needs to distribute the balls into the baskets such that the minimum magnetic force<\/strong> between any two balls is maximum<\/strong>.<\/p>\n\n\n\n

Rick stated that magnetic force between two different balls at positions x<\/code> and y<\/code> is |x - y|<\/code>.<\/p>\n\n\n\n

Given the integer array position<\/code> and the integer m<\/code>. Return the required force<\/em>.<\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> position = [1,2,3,4,7], m = 3\nOutput:<\/strong> 3\nExplanation:<\/strong> Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> position = [5,4,3,2,1,1000000000], m = 2\nOutput:<\/strong> 999999999\nExplanation:<\/strong> We can use baskets 1 and 1000000000.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == position.length<\/code><\/li>
  • 2 <= n <= 10^5<\/code><\/li>
  • 1 <= position[i] <= 10^9<\/code><\/li>
  • All integers in position<\/code> are distinct<\/strong>.<\/li>
  • 2 <= m <= position.length<\/code><\/li><\/ul>\n\n\n\n
    Solution: Binary Search<\/strong><\/h2>\n\n\n\n
    Find the max distance that we can put m balls.<\/p>\n\n\n\n
    Time complexity: O(n*log(distance))
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int maxDistance(vector& position, int m) {\n    const int n = position.size();\n    sort(begin(position), end(position));\n    auto count = [&](int d) -> int {\n      int last = position[0];\n      int ans = 1;\n      for (int x : position) {\n        if (x - last >= d) {\n          last = x;\n          ++ans;\n        }\n      }\n      return ans;\n    };\n    int l = 0;\n    int t = (position.back() - position.front()) + 1;\n    int r = t;\n    while (l < r) {\n      int mid = l + (r - l) \/ 2;\n      if (count(t - mid) >= m) \/\/ find min of l => max of t - l\n        r = mid;\n      else\n        l = mid + 1;\n    }\n    return t - l;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \nclass Solution {\n  public int maxDistance(int[] position, int m) {\n    Arrays.sort(position);\n    final int n = position.length;\n    int l = 0;\n    int r = position[n - 1] - position[0] + 1;\n    int t = r;\n    while (l < r) {\n      int mid = l + (r - l) \/ 2;\n      if (getCount(position, t - mid) >= m)\n        r = mid;\n      else\n        l = mid + 1;\n    }\n    return t - l;\n  }\n  \n  private int getCount(int[] position, int d) {\n    int count = 1;\n    int last = position[0];\n    for (int x : position) {\n      if (x - last >= d) {\n        ++count;\n        last = x;\n      }\n    }\n    return count;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def maxDistance(self, position: List[int], m: int) -> int:\n    position.sort()\n    def getCount(d: int) -> int:\n      last, count = position[0], 1\n      for x in position:\n        if x - last >= d:\n          last = x\n          count += 1\n      return count\n    l, r = 0, position[-1] - position[0] + 1\n    t = r\n    while l < r:\n      mid = l + (r - l) \/\/ 2\n      if getCount(t - mid) >= m:\n        r = mid\n      else:\n        l = mid + 1\n    return t - l\n        \n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177],"class_list":["post-7253","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7253","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=7253"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7253\/revisions"}],"predecessor-version":[{"id":7258,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7253\/revisions\/7258"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}