{"id":7125,"date":"2020-07-19T01:02:01","date_gmt":"2020-07-19T08:02:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7125"},"modified":"2020-07-19T01:02:46","modified_gmt":"2020-07-19T08:02:46","slug":"leetcode-1521-find-a-value-of-a-mysterious-function-closest-to-target","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-1521-find-a-value-of-a-mysterious-function-closest-to-target\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target"},"content":{"rendered":"\n
\"\"\/<\/figure>\n\n\n\n

Winston was given the above mysterious function func<\/code>. He has an integer array arr<\/code> and an integer target<\/code> and he wants to find the values l<\/code> and r<\/code> that make the value |func(arr, l, r) - target|<\/code> minimum possible.<\/p>\n\n\n\n

Return the minimum possible value<\/em> of |func(arr, l, r) - target|<\/code>.<\/p>\n\n\n\n

Notice that func<\/code> should be called with the values l<\/code> and r<\/code> where 0 <= l, r < arr.length<\/code>.<\/p>\n\n\n\n

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

Input:<\/strong> arr = [9,12,3,7,15], target = 5\nOutput:<\/strong> 2\nExplanation:<\/strong> Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1000000,1000000,1000000], target = 1\nOutput:<\/strong> 999999\nExplanation:<\/strong> Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,2,4,8,16], target = 0\nOutput:<\/strong> 0\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr.length <= 10^5<\/code><\/li>
  • 1 <= arr[i] <= 10^6<\/code><\/li>
  • 0 <= target <= 10^7<\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force w\/ Optimization<\/strong><\/h2>\n\n\n\n
    Try all possible [l, r] range with pruning. 
    1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
    2. Case 1, s = arr[l] & … & arr[n-1], s > target, 
        Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
        if s > target, then s’ > target, we can stop outer loop as well.
       Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.<\/p>\n\n\n\n
    Time complexity: O(n)? on average, O(n^2) in worst case.
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int closestToTarget(vector& arr, int target) {\n    const int n = arr.size();\n    int ans = INT_MAX;\n    for (int i = 0; i < n; ++i) {\n      int s = arr[i];\n      for (int j = i; j < n; ++j) {\n        s &= arr[j];\n        ans = min(ans, abs(s - target));\n        if (ans == 0) return 0;\n        if (s <= target) break; \/\/ s is decreasing.\n      }\n      if (s > target) break; \/\/ s is increasing.\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) -…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[52,16,217,215],"class_list":["post-7125","post","type-post","status-publish","format-standard","hentry","category-bit","tag-binary-search","tag-bit","tag-hard","tag-sliding-window","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7125","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=7125"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7125\/revisions"}],"predecessor-version":[{"id":7127,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7125\/revisions\/7127"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}