{"id":7025,"date":"2020-07-05T08:29:08","date_gmt":"2020-07-05T15:29:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7025"},"modified":"2020-07-08T17:24:49","modified_gmt":"2020-07-09T00:24:49","slug":"leetcode-1502-can-make-arithmetic-progression-from-sequence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1502-can-make-arithmetic-progression-from-sequence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1502. Can Make Arithmetic Progression From Sequence"},"content":{"rendered":"\n

Given an array of numbers arr<\/code>. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.<\/p>\n\n\n\n

Return true<\/code> if the array can be rearranged to form an arithmetic progression, otherwise, return false<\/code>.<\/p>\n\n\n\n

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

Input:<\/strong> arr = [3,5,1]\nOutput:<\/strong> true\nExplanation: <\/strong>We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,2,4]\nOutput:<\/strong> false\nExplanation: <\/strong>There is no way to reorder the elements to obtain an arithmetic progression.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= arr.length <= 1000<\/code><\/li>
  • -10^6 <= arr[i] <= 10^6<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Sort and check.<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlog)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool canMakeArithmeticProgression(vector& arr) {\n    sort(begin(arr), end(arr));\n    const int diff = arr[1] - arr[0];\n    for (int i = 2; i < arr.size(); ++i)\n      if (arr[i] - arr[i - 1] != diff) return false;\n    return true;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\n  public boolean canMakeArithmeticProgression(int[] arr) {\n    Arrays.sort(arr);\n    int diff = arr[1] - arr[0];\n    for (int i = 2; i < arr.length; ++i)\n      if (arr[i] - arr[i - 1] != diff) return false;\n    return true;\n  }\n}\n<\/pre>\n\n<\/div>
    python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def canMakeArithmeticProgression(self, arr: List[int]) -> bool:\n    arr.sort()\n    diff = arr[1] - arr[0]\n    return all(i - j == diff for i, j in zip(arr[1:], arr[:-1]))\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Rearrange the array<\/strong><\/h2>\n\n\n\n
    Find min \/ max \/ diff and put each element into its correct position by swapping elements in place.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool canMakeArithmeticProgression(vector& arr) {\n    const int n = arr.size();\n    const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr));\n    const auto [lo, hi] = pair{*loit, *hiit};\n    if ((hi - lo) % (n - 1)) return false;\n    const int diff = (hi - lo) \/ (n - 1);\n    if (diff == 0) return true;\n    for (int i = 0; i < n; ++i) {\n      if ((arr[i] - lo) % diff) return false;\n      const int idx = (arr[i] - lo) \/ diff;\n      if (idx != i) swap(arr[i--], arr[idx]);\n    }\n    return true;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same. Return true if the…<\/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":[20,222,273,290],"class_list":["post-7025","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-easy","tag-in-place","tag-swap","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7025","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=7025"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7025\/revisions"}],"predecessor-version":[{"id":7053,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7025\/revisions\/7053"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}