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

[mohammadfraz]

you can think s1 as dp[i] := {A[i], A[i] & A[i – 1], A[i] & A[i – 1] & A[i – 2], …, A[i] & A[i – 1] & … & A[0]}, bitwise ANDs of all subarrays end with A[i]. Then dp[i+1] = {A[i+1] & b, for every b in the set of dp[i]} + A[i+1], where here we call s2 as dp[i+1].
On a first glance, it seems size of dp is O(n), and therefore to calculate one dp needs O(n) time. Looping all dps will give O(n^2) time. But actually, size(dp) <= 32, the maxium number of bits in a int variable. This because: All the elements (in the order of above sequence) in dp[i] is non-increasing by flipping 1 bits to 0 from A[i]. Since there are at most 32 1s in A[i]. Thus the size of the set is <= 32.

[mohdsaadalikhan]

Which topic does this question belong to dp or binary search?

[vikasgautam]

bro can u please provide solution for Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.PLEASE.

[code]

if say 27 bits are set in number 1, then taking its *and* with n numbers can produce around 27!=~n numbers ? can u please simplify complexity properly.

[ayushgarg]

Please make a video on max. XOR pair and max.XOR subsequence

[harshbhatia]

what software are you using for this video