Number of Subarrays With AND Value of K - Problem

Given an array of integers nums and an integer k, return the number of subarrays of nums where the bitwise AND of the elements of the subarray equals k.

A subarray is a contiguous sequence of elements within an array.

The bitwise AND operation combines corresponding bits of integers using the AND logic gate. For example, 5 & 3 = 1 because 101 & 011 = 001.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,3,7,3], k = 3

› Output: 5

💡 Note: Subarrays with AND = 3: [3] at index 1, [3,7] from indices 1-2, [7,3] from indices 2-3, [3] at index 3, and [3,7,3] from indices 1-3. Total: 5 subarrays.

Example 2 — Single Element

$ Input: nums = [1,1,1], k = 1

› Output: 6

💡 Note: All subarrays have AND = 1: three single elements [1], two pairs [1,1], and one triplet [1,1,1]. Total: 3+2+1=6.

Example 3 — No Valid Subarrays

$ Input: nums = [1,2,4], k = 8

› Output: 0

💡 Note: No subarray can have AND = 8 since the maximum element is 4, and AND operations can only make values smaller.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is that AND operations can only turn bits OFF, never ON. This means the number of distinct AND values starting from any position is limited to at most log(max_value). The optimal approach uses bit manipulation with set tracking to maintain distinct AND values efficiently. Time: O(n log W), Space: O(log W) where W is the maximum element value.

Common Approaches

✓ Bit Manipulation with Set Tracking

⏱️ Time: O(n log W) Space: O(log W)

Since AND operations can only turn bits off, the number of distinct AND values starting from any position is limited. We track these distinct values as we extend subarrays.

Brute Force - Check All Subarrays

⏱️ Time: O(n³) Space: O(1)

For each starting position, extend the subarray one element at a time, computing the AND of all elements. Count subarrays where the AND equals k.

Optimized AND Calculation

⏱️ Time: O(n²) Space: O(1)

For each starting position, maintain the running AND as we extend the subarray. This eliminates the need to recalculate AND from scratch for each subarray.

Bit Manipulation with Set Tracking — Algorithm Steps

For each position, maintain set of possible AND values
When extending, AND each existing value with new element
Remove duplicates and count matches with k
Key insight: at most 32 distinct values (number of bits)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Set

Start with current element in set

Update Set

AND each value in set with next element

Count & Prune

Count matches and remove duplicates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int andValues[64];
        int andSize = 1;
        andValues[0] = nums[i];
        if (nums[i] == k) {
            count++;
        }
        
        for (int j = i + 1; j < numsSize; j++) {
            int newAndValues[64];
            int newAndSize = 0;
            
            for (int l = 0; l < andSize; l++) {
                int newVal = andValues[l] & nums[j];
                int found = 0;
                for (int m = 0; m < newAndSize; m++) {
                    if (newAndValues[m] == newVal) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    newAndValues[newAndSize++] = newVal;
                    if (newVal == k) {
                        count++;
                    }
                }
            }
            
            andSize = newAndSize;
            for (int l = 0; l < andSize; l++) {
                andValues[l] = newAndValues[l];
            }
        }
    }
    
    return count;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log W)

For each element, at most log W distinct AND values (W = max element value)

⚠ Quadratic Growth

Space Complexity

O(log W)

Set stores at most log W distinct AND values at any time

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Subarrays With AND Value of K - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation with Set Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler