Last Updated: 23 Nov, 2021

Count Subarrays With K Ones

Moderate

Asked in companies

Solve now

Problem statement

You are given a binary array 'arr' of length 'N' and an integer 'k'. Return the number of subarrays having the count of 1's equal to ‘k’.

Example :

Let the array 'arr' be: [1, 0, 1].
Let ‘k’ be: 1

Then the subarrays having the number of ones equal to ‘k’ will be: [1], [1,0], [0,1], [1].

Input Format :

The first line contains two single space-separated integers 'N' and 'k'.

The second line contains 'N' space-separated integers, denoting the elements of array 'arr'.

Output Format :

The output contains the number of subarrays with the count of  1's equal to ‘k’.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

Approach:

This approach is a brute-force solution to count the number of subarrays with a given sum 'k' in the binary array 'arr'. It uses nested loops to check all possible subarrays, resulting in a less efficient algorithm.

Here is the algorithm:

Create a variable (say, ‘res’) to store the number of subarrays.
Run a loop from 0 to ‘N’ (say, iterator ‘i’).
- Create a variable (say, ‘cnt’) to store the count of ones in a subarray.
- Run a loop from ‘i’ to ‘N’ (say, iterator ‘j’).
  - Check if ‘arr[j]’ is equal to 1.
    - Increment ‘cnt’ by 1.
  - Check if ‘cnt’ is equal to ‘K’.
    - Increment ‘RES’ by 1.
  - Check if ‘cnt’ is greater than ‘K’.
    - Break.
Return ‘res’.

Solve now

02 Approach

Approach:

The algorithm uses a prefix sum array and a hashmap to count the number of subarrays with a given sum 'k' in a binary array 'arr'. It maintains a variable cnt to track the count of ones encountered so far and a variable res to store the count of subarrays. The prefix sum array prefix is used to keep track of the count of each prefix sum encountered during traversal. By comparing the current count cnt with the given sum 'k', the algorithm updates the result res by adding the count of subarrays that have the desired sum. Finally, it returns the count res as the answer.

Here is the algorithm :

Create a variable (say, ‘res’) to store the number of subarray.
Create a variable (say, ‘cnt’) to store the sum or count.
Create an array (say, ‘prefix’) of size ‘N’, to store the prefix sum and initialize it with 0.
Update ‘prefix[0]’ to 1.
Run a loop from 0 to ‘N’ (say, iterator ‘i’) to traverse the array.
- Add the current value in ‘cnt’.
- Check if ‘cnt’ is greater than equal to ‘k’,
  - Update ‘res’ by adding ‘prefix[cnt - k]’ to it.
- Increment ‘prefix[cnt]’ by 1.
Return ‘res’.

Solve now