Frontend School

Count Subarrays with K Set Bits in Bitwise OR

DSA
hard

Count Subarrays with K Set Bits in Bitwise OR

Hard
Bit Manipulation
Arrays
Subarrays
Sliding Window

Overview

In data processing and network protocols, analyzing bit patterns within sequences of data is crucial for tasks like error detection, packet filtering, or optimizing storage. This problem asks you to identify and count specific subarrays based on a bitwise property of their elements' aggregate. It challenges your understanding of bitwise operations and efficient array traversal.

What you need to do / Task

You are given an array of non-negative integers nums and a target integer k. Your task is to find the total number of subarrays [i, j] (where 0 <= i <= j < nums.length) such that the bitwise OR of all elements nums[x] for i <= x <= j results in a value that has exactly k set bits.

Input & output

  • Input:
    • nums: An array of non-negative integers.
    • k: An integer representing the target number of set bits.
  • Output:
    • Return a single integer, the total count of subarrays whose bitwise OR sum has exactly k set bits.

Clarifications

  • An empty array nums is not possible per constraints (nums.length >= 1).
  • If k is 0, you are looking for subarrays whose bitwise OR sum is 0 (i.e., all elements in the subarray are 0).
  • The maximum value of nums[i] is up to 10^9, meaning numbers can have up to 30 bits set. Consequently, k will not exceed 30.

Examples

1

Example 1

Input:

nums = [1, 2, 3], k = 2

Output:

4

Note:

Let's analyze subarrays and their bitwise OR sums:

  • [1]: OR sum = 1 (binary 01), 1 set bit.
  • [2]: OR sum = 2 (binary 10), 1 set bit.
  • [3]: OR sum = 3 (binary 11), 2 set bits. (Count = 1)
  • [1, 2]: OR sum = (1 | 2) = 3 (binary 11), 2 set bits. (Count = 2)
  • [2, 3]: OR sum = (2 | 3) = 3 (binary 11), 2 set bits. (Count = 3)
  • [1, 2, 3]: OR sum = (1 | 2 | 3) = 3 (binary 11), 2 set bits. (Count = 4) Total subarrays with 2 set bits in their OR sum: 4.
2

Example 2

Input:

nums = [0, 0, 0], k = 0

Output:

6

Note:

All elements are 0. The bitwise OR sum of any subarray will be 0, which has 0 set bits. There are N*(N+1)/2 subarrays in an array of length N. For N=3, there are 3*(3+1)/2 = 6 subarrays. All 6 subarrays satisfy the condition (OR sum is 0, which has k=0 set bits).

3

Example 3

Input:

nums = [7, 5, 2], k = 1

Output:

1

Note:

Binary representations: 7 (111), 5 (101), 2 (010).

  • [7]: OR sum = 7 (3 set bits).
  • [5]: OR sum = 5 (2 set bits).
  • [2]: OR sum = 2 (1 set bit). (Count = 1)
  • [7, 5]: OR sum = (7 | 5) = 7 (3 set bits).
  • [5, 2]: OR sum = (5 | 2) = 7 (3 set bits).
  • [7, 5, 2]: OR sum = (7 | 5 | 2) = 7 (3 set bits). Only one subarray ([2]) has an OR sum with exactly 1 set bit.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 30

Out of scope

  • Input validation beyond the given constraints.
  • Handling of negative numbers in nums (they are guaranteed non-negative).

What interviewers evaluate

  • Algorithmic Efficiency: The solution must be more efficient than a naive O(N^2) approach, considering nums.length up to 10^5.
  • Bit Manipulation Proficiency: Correct and effective use of bitwise operations and bit counting techniques.
  • Edge Case Handling: Properly handles scenarios like k=0, all elements being zero, or arrays with a single element.
  • Code Quality: Writes clean, readable, and well-structured code with appropriate comments where necessary.

Loading editor...