LC-3209 Hard LeetCode

3209. Number of Subarrays With AND Value of K

Array Binary Search Bit Manipulation Segment Tree

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 34% Topics: Array, Binary Search, Bit Manipulation, Segment Tree

Reading material

Arrays & Hashing 12 min Binary Search 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(nlogr)
# Space: O(logr)

import collections


# dp, lc3171
class Solution(object):
    def countSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = 0
        dp = collections.defaultdict(int)
        for x in nums:
            new_dp = collections.defaultdict(int)
            if x&k == k:
                new_dp[x] += 1
                for y, c in dp.iteritems():
                    new_dp[y&x] += c
                if k in new_dp:
                    result += new_dp[k]                
            dp = new_dp
        return result

Solution from kamyu104/LeetCode-Solutions · MIT