Count Subarrays With K Ones

Moderate
0/80
Average time to solve is 23m
profile
Contributed by
35 upvotes
Asked in companies
OlaMedia.netAmazon

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].
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
4 2
1 1 0 1
Sample output 1 :
3
Explanation For Sample Output 1 :
The subarrays having the number of ones equal to 2 will be: [1,1], [1,1,0], [1,0,1].

So the count is 3.
Sample Input 2 :
5 1
1 0 0 1 0
Sample output 2 :
9
Constraints :
1 <= 'N' <= 10^4

arr[i] is either 0 or 1.

0 <= 'k' <= 10^6

Time limit: 1 sec
Hint

Check for every possible subarray present in an array. 

Approaches (2)
Brute Force

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:

 

  1. Create a variable (say, ‘res’) to store the number of subarrays.
  2. 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.
  3. Return ‘res’.
Time Complexity

O(N^2), where ‘N’ is the length of the given array.

 

The nested loops result in a time complexity of O(N^2) because for each index 'i', the algorithm iterates through all possible subarrays starting from that index.

Space Complexity

O(1)

 

We don’t use any extra space. Therefore, the overall space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count Subarrays With K Ones
Full screen
Console