Number of Subarrays With AND Value of K - Practice Coding Problems

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: 3

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

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

Understanding the Visualization

Input

Array [5,3,7,3] and target k=3

Process

Check all subarrays and compute AND values

Output

Count of subarrays with AND = k

Key Takeaway

🎯 Key Insight: AND operations can only decrease values, so we can efficiently prune impossible branches

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

Approach	Time	Space	Notes
✓ Optimized AND Calculation	O(n²)	O(1)	Compute AND incrementally while extending subarrays
Bit Manipulation with Set Tracking	O(n log W)	O(log W)	Track distinct AND values efficiently using bit properties
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and compute its AND value

Optimized AND Calculation — Algorithm Steps

For each starting index i
Initialize AND result with nums[i]
Extend subarray by updating AND incrementally
Count when AND equals k

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin with single element

Extend & Update

Add next element and update AND

Check & Count

If AND equals k, increment counter

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 andResult = nums[i];
        if (andResult == k) {
            count++;
        }
        
        for (int j = i + 1; j < numsSize; j++) {
            andResult &= nums[j];
            if (andResult == k) {
                count++;
            }
        }
    }
    
    return count;
}

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²)

Two nested loops, but AND computed incrementally in O(1)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized AND Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler