1521. Find a Value of a Mysterious Function Closest to Target Hard

1/**
2 * [1521] Find a Value of a Mysterious Function Closest to Target
3 *
4 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/change.png" style="width: 635px; height: 312px;" />
5 * 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) - target| minimum possible.
6 * Return the minimum possible value of |func(arr, l, r) - target|.
7 * Notice that func should be called with the values l and r where 0 <= l, r < arr.length.
8 *  
9 * Example 1:
10 * 
11 * Input: arr = [9,12,3,7,15], target = 5
12 * Output: 2
13 * Explanation: 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.
14 * 
15 * Example 2:
16 * 
17 * Input: arr = [1000000,1000000,1000000], target = 1
18 * Output: 999999
19 * Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
20 * 
21 * Example 3:
22 * 
23 * Input: arr = [1,2,4,8,16], target = 0
24 * Output: 0
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= arr.length <= 10^5
30 * 	1 <= arr[i] <= 10^6
31 * 	0 <= target <= 10^7
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
37// discuss: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn closest_to_target(arr: Vec<i32>, target: i32) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_1521() {
55    }
56}
57