Problem statement

https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

Solution

let dp[i] be all possible values of function, ending with element with index i. In fact there can be only O(log M) different values, where M is the biggest number: because when we add one more number to the left number of 1 bits can only decrease or number stays the same. So what we need to is to update dp and each time look for smallest distance to target.

Complexity

Time complexity is O(n*log M), space is O(log M).

Code

class Solution:
    def closestToTarget(self, arr, target):
        dp, ans = set(), float('inf')
        for a in arr:
            dp = {a & b for b in dp} | {a}
            for c in dp: ans = min(ans, abs(c - target))
        return ans

Remark

It is very similar to problem 0898