Jobs

Interviews

Discussions

Number of Subarrays With AND Value of K

Hard

Asked by:

5 views

Topics:

ArraysBit ManipulationSliding Windows

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.

Example 1:

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

Output: 6

Explanation:

All subarrays contain only 1's.

Example 2:

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

Output: 3

Explanation:

Subarrays having an AND value of 1 are: [1,1,2], [1,1,2], [1,1,2].

Example 3:

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

Output: 2

Explanation:

Subarrays having an AND value of 2 are: [1,2,3], [1,2,3].

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i], k <= 10⁹

Number of Subarrays With AND Value of K

Hard

Asked by:

5 views

Topics:

ArraysBit ManipulationSliding Windows

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.

Example 1:

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

Output: 6

Explanation:

All subarrays contain only 1's.

Example 2:

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

Output: 3

Explanation:

Subarrays having an AND value of 1 are: [1,1,2], [1,1,2], [1,1,2].

Example 3:

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

Output: 2

Explanation:

Subarrays having an AND value of 2 are: [1,2,3], [1,2,3].

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i], k <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`?
Can the array `nums` contain negative numbers or zeros?
What should I return if no subarray has a bitwise AND equal to `k`?
Are overlapping subarrays considered distinct, and should each be counted if their bitwise AND equals `k`?
Is the order of elements within a subarray important, or are we only concerned with the contiguous sequence of numbers?

Brute Force Solution

Approach

The brute force method involves checking every possible group of consecutive numbers within the given list. For each group, we'll calculate their combined 'AND' value and see if it matches our target number.

Here's how the algorithm would work step-by-step:

First, consider every possible starting point in your list of numbers.
From each starting point, form a group of one number, then a group of two consecutive numbers, then three, and so on, until you reach the end of the list.
For each of these groups, calculate the 'AND' value. This means performing a special calculation on all the numbers in the group to combine them into one number.
Compare this combined 'AND' value with the target number we're looking for.
If the combined value matches the target number, count that group as a valid group.
Repeat this process for every possible starting point and group size.
In the end, simply add up the number of valid groups you've found. That's your answer.

Code Implementation

def number_of_subarrays_with_k_brute_force(numbers, target):
    number_of_subarrays = 0

    for start_index in range(len(numbers)):
        # Iterate through all possible start indices

        for end_index in range(start_index, len(numbers)):
            # Iterate to create subarrays of increasing length
            current_and_value = numbers[start_index]

            for index in range(start_index + 1, end_index + 1):
                # Calculate the AND value for the current subarray
                current_and_value &= numbers[index]

            if current_and_value == target:
                # Check if current and value is equal to target.
                number_of_subarrays += 1

    return number_of_subarrays

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays. The outer loop iterates 'n' times, where 'n' is the number of elements in the input array. For each element in the outer loop, the inner loop iterates up to 'n' times to form and evaluate subarrays starting from that element. Thus, the nested loops result in approximately n * n/2 operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The described brute force approach iterates through all possible subarrays, calculating the AND value for each. It doesn't explicitly create any auxiliary data structures to store intermediate subarrays or other data dependent on the input size N. Only a few variables are used to keep track of the current subarray's AND value and loop indices. Therefore, the space complexity remains constant regardless of the input array's size, resulting in O(1) space complexity.

Optimal Solution

Approach

The goal is to efficiently count the sections that have a specific AND value. We do this by only tracking segments that *could* have that value and efficiently discarding those that can't, avoiding unnecessary checks.

Here's how the algorithm would work step-by-step:

Go through each number in the list one at a time.
For each number, check if it's possible for the sections ending there to have the target AND value. If the number is smaller than the target, then it is not possible for it to contribute to the count.
If the number is equal to or larger than the target, start looking back at previous numbers to see which sections ending at the current position have the target AND value.
When looking back, keep a running AND value of the numbers you've seen. If the running AND value is bigger than the target, there is no reason to continue looking back as the AND value will only ever decrease.
If the running AND value equals the target, then you've found a valid section, so increase the count.
If the running AND value becomes smaller than the target, stop looking back because it's no longer possible to reach the target by adding more numbers.

Code Implementation

def count_subarrays_with_and_value(numbers, target_and):
    subarray_count = 0
    for i in range(len(numbers)):
        #If the current number is less than target, no subarrays end here.
        if numbers[i] < target_and:
            continue

        current_and = numbers[i]
        # If current number equals target, increment counter.
        if current_and == target_and:
            subarray_count += 1

        #Iterate backwards to find valid subarrays.
        for j in range(i - 1, -1, -1):
            current_and &= numbers[j]

            #Stop if current_and becomes less than target.
            if current_and < target_and:
                break

            # Only count if current_and matches target.
            if current_and == target_and:
                subarray_count += 1

    return subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. Within the outer loop, there's a while loop that iterates backward. However, each element is considered at most once in this inner loop because if the running AND value becomes smaller than the target, the inner loop breaks and that starting point is never revisited. Therefore, the inner loop's total iterations across the entire algorithm cannot exceed n, making the overall time complexity O(n).

Space Complexity

O(1) – The algorithm iterates through the input list without using any auxiliary data structures that scale with the input size N. It only uses a few variables to store the running AND value and to iterate through the array. The space used by these variables remains constant irrespective of the input size N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array nums	Return 0, as no subarrays can be formed.
Null input array nums	Throw an IllegalArgumentException or return 0 depending on the requirements.
k is zero	The solution needs to correctly identify subarrays where the bitwise AND results in zero.
k is negative	Bitwise AND operations typically involve only non-negative numbers; handle appropriately (e.g., return 0, or handle as a regular integer).
Array contains only zeros and k is non-zero	The number of subarrays will always be 0, return it immediately.
All elements in nums are less than k	The number of subarrays will always be 0, so return 0.
Integer overflow during bitwise AND operations with large numbers in nums	Ensure the data type used for the bitwise AND can accommodate the range of possible values.
Large input array nums to test the time complexity	The solution should ideally have O(n) or O(n log n) time complexity to handle large inputs efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`?
Can the array `nums` contain negative numbers or zeros?
What should I return if no subarray has a bitwise AND equal to `k`?
Are overlapping subarrays considered distinct, and should each be counted if their bitwise AND equals `k`?
Is the order of elements within a subarray important, or are we only concerned with the contiguous sequence of numbers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible starting point in your list of numbers.
From each starting point, form a group of one number, then a group of two consecutive numbers, then three, and so on, until you reach the end of the list.
For each of these groups, calculate the 'AND' value. This means performing a special calculation on all the numbers in the group to combine them into one number.
Compare this combined 'AND' value with the target number we're looking for.
If the combined value matches the target number, count that group as a valid group.
Repeat this process for every possible starting point and group size.
In the end, simply add up the number of valid groups you've found. That's your answer.

Code Implementation

def number_of_subarrays_with_k_brute_force(numbers, target):
    number_of_subarrays = 0

    for start_index in range(len(numbers)):
        # Iterate through all possible start indices

        for end_index in range(start_index, len(numbers)):
            # Iterate to create subarrays of increasing length
            current_and_value = numbers[start_index]

            for index in range(start_index + 1, end_index + 1):
                # Calculate the AND value for the current subarray
                current_and_value &= numbers[index]

            if current_and_value == target:
                # Check if current and value is equal to target.
                number_of_subarrays += 1

    return number_of_subarrays

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each number in the list one at a time.
For each number, check if it's possible for the sections ending there to have the target AND value. If the number is smaller than the target, then it is not possible for it to contribute to the count.
If the number is equal to or larger than the target, start looking back at previous numbers to see which sections ending at the current position have the target AND value.
When looking back, keep a running AND value of the numbers you've seen. If the running AND value is bigger than the target, there is no reason to continue looking back as the AND value will only ever decrease.
If the running AND value equals the target, then you've found a valid section, so increase the count.
If the running AND value becomes smaller than the target, stop looking back because it's no longer possible to reach the target by adding more numbers.

Code Implementation

def count_subarrays_with_and_value(numbers, target_and):
    subarray_count = 0
    for i in range(len(numbers)):
        #If the current number is less than target, no subarrays end here.
        if numbers[i] < target_and:
            continue

        current_and = numbers[i]
        # If current number equals target, increment counter.
        if current_and == target_and:
            subarray_count += 1

        #Iterate backwards to find valid subarrays.
        for j in range(i - 1, -1, -1):
            current_and &= numbers[j]

            #Stop if current_and becomes less than target.
            if current_and < target_and:
                break

            # Only count if current_and matches target.
            if current_and == target_and:
                subarray_count += 1

    return subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array nums	Return 0, as no subarrays can be formed.
Null input array nums	Throw an IllegalArgumentException or return 0 depending on the requirements.
k is zero	The solution needs to correctly identify subarrays where the bitwise AND results in zero.
k is negative	Bitwise AND operations typically involve only non-negative numbers; handle appropriately (e.g., return 0, or handle as a regular integer).
Array contains only zeros and k is non-zero	The number of subarrays will always be 0, return it immediately.
All elements in nums are less than k	The number of subarrays will always be 0, so return 0.
Integer overflow during bitwise AND operations with large numbers in nums	Ensure the data type used for the bitwise AND can accommodate the range of possible values.
Large input array nums to test the time complexity	The solution should ideally have O(n) or O(n log n) time complexity to handle large inputs efficiently.