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

Problem Explanation

The question asks us to find value of l, r (0 <= l, r < arr.length) such that difference between result of given function and target is minimum.

Winston was given the above mysterious function "func". The function takes array arr and two more variables l and r as input. Winston has an integer array arr and an integer target. He can take any value of l and r. The task is to find two values of l and r that when passed into the function, the result of the function is closest to the target value.

Let's take an example to have deep understanding of question:

Say arr = [9,12,3,7,15], target = 5 so in this case if we run all possible pairs through the mysterious function "func" we get [9, 12, 3, 7, 15, 8, 0, 3, 7, 0, 0, 3, 0, 0, 0] as the output. The closest values to 5 in these are 7 and 3 so, the minimum difference is 2.

Approach / Solution

We can collect the bitwise and of the previous numbers in a set, which is the result we can get. For the answer, we only need to choose the closest to the target one.

Algorithm:

1. Initialize answer = "infinity".
2. create empty set s.
3. Iterate over each number in array
   1. create new empty set s2
   2. add each number from set s into set s2 after performing bitwise and operation with it and a
   3. set s = s2
   4. at end of each iteration, add a to set s.
   5. for every c in s, assign the difference between it and target to answer if it is smaller than the previous answer.

Python Solution

1
2python
3class Solution:
4    def closestToTarget(self, arr: List[int], target: int) -> int:
5        ans = float('inf')
6        # S(j) := arr[i] & arr[i + 1] & ... & arr[j] for all 0 <= i <= j (fixed)
7        s = set()
8
9        for a in arr:
10            s = {a & b for b in s} | {a}
11            ans = min(ans, *(abs(c - target) for c in s))
12        return ans

Java Solution

1
2java
3class Solution {
4    public int closestToTarget(int[] arr, int target) {
5        int ans = Integer.MAX_VALUE;
6        Set<Integer> s = new HashSet<>();
7        for (int a : arr) {
8            Set<Integer> s2 = new HashSet<>();
9            for (int b : s)
10                s2.add(a & b);
11            s2.add(a);
12            for (int c : s2)
13                ans = Math.min(ans, Math.abs(c - target));
14            s = s2;
15        }
16        return ans;
17    }
18}

JavaScript Solution

1
2javascript
3var closestToTarget = function (arr, target) {
4    let ans = Number.MAX_SAFE_INTEGER;
5    let s = new Set();
6
7    for (let a of arr) {
8        let s2 = new Set();
9        for (let b of s) {
10            s2.add(a & b);
11        }
12        s2.add(a);
13        for (let c of s2) {
14            ans = Math.min(ans, Math.abs(c - target));
15        }
16        s = s2;
17    }
18    return ans;
19};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int closestToTarget(vector<int>& arr, int target) {
6        int ans = INT_MAX;
7        unordered_set<int> s;
8        for (const int a : arr) {
9          unordered_set<int> s2{a};
10          for (const int b : s)
11            s2.insert(a & b);
12          for (const int c : s = s2)
13            ans = min(ans, abs(c - target));
14        }
15        return ans;
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public int ClosestToTarget(int[] arr, int target) {
5        int ans = int.MaxValue;
6        HashSet<int> s = new HashSet<int>();
7        foreach (int a in arr) {
8            HashSet<int> s2 = new HashSet<int>();
9            foreach (int b in s) {
10                s2.Add(a & b);
11            }
12            s2.Add(a);
13            foreach (int c in s2) {
14                ans = Math.Min(ans, Math.Abs(c - target));
15            }
16            s = s2;
17        }
18        return ans;
19    }
20}

Go Solution

In Go, we create two slices, each initialized with the capacity equivalent to the length of the input array. We also assign the absolute difference between the first element of the array and the target to answer. We then loop through all elements in the array starting from the second element, on each iteration creating a new slice set s where each element is a bitwise AND of the current element and each element from previous set. Then, we calculate the difference between all resultants and the target and if it is less than the current answer then assign it to answer. Repeat this process until all elements have been covered.

1
2go
3package main
4
5import (
6	"fmt"
7	"math"
8)
9
10func closestToTarget(arr []int, target int) int {
11	var answer = math.Abs(float64(arr[0] - target))
12	var s = make([]int, len(arr))
13	s[0] = arr[0]
14	var lenS = 1
15	for _, a := range arr[1:] {
16		var s2 = make([]int, 0, len(arr))
17		var uMap = make(map[int]bool)
18		for _, b := range s[:lenS] {
19			uMap[a&b] = true
20		}
21		uMap[a] = true
22		for k := range uMap {
23			s2 = append(s2, k)
24			answer = math.Min(answer, math.Abs(float64(k-target)))
25		}
26		s = s2
27		lenS = len(s)
28	}
29	return int(answer)
30}
31
32func main() {
33	var dataTest = []struct {
34		arr    []int
35		target int
36	}{
37		{arr: []int{9, 12, 3, 7, 15}, target: 5},
38		{arr: []int{5, 89, 79, 44, 45, 79}, target: 965},
39	}
40	for _, data := range dataTest {
41		var v = closestToTarget(data.arr, data.target)
42		fmt.Println(v)
43	}
44}

In conclusion, the approach of using a set to collect all possible values from the bitwise AND operation on array elements and then finding the minimum difference from the target provides an efficient solution. This approach preserves memory because we do not store duplicate results from the AND operation. Various programming languages offer different methods to find the minimum difference, but the core logic remains the same. All solutions operate in linear time and space complexities, which are O(n) and O(n) respectively.