Count of subarrays which contains a given number exactly K times

0 0 6 minutes read

Given an array A[] of N elements consisting of values from 1 to N with duplicates, the task is to find the total number of subarrays that contain a given number num exactly K times.

Examples:

Input: A[] = {1, 2, 1, 5, 1}, num = 1, K = 2
Output: 2
Explanation:
Subarrays {1, 2, 1, 5}, {1, 2, 1}, {2, 1, 5, 1} and {1, 5, 1} contains 1 exactly twice.

Input: A[] = {1, 5, 3, 5, 7, 5, 6, 5, 10, 5, 12, 5}, num = 5, K = 3
Output: 14

Naive Approach: A simple solution is to generate all the subarrays of the given array and count the number of subarrays in which the given number occurs exactly K times.

Time complexity: O(N²) where N is the size of the given array.

Efficient Approach:

Store the indices which contain the given number num.
Traverse the indices[] array and calculate the number of subarrays possible for every K indices.
The number of subarrays possible for any K indices of num is equal to the

Product of (i^th index – (i-1)^th index) and ( (i + K)^th index – (i+(K – 1))^th index)

The count of all such subarrays gives the count of the total possible subarrays in the given array.

Below is the implementation of the above approach:

C++

// C++ program to count subarrays
// which contains a given number
// exactly K times
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// the count of subarrays
// which contains given
// number exactly K times
int countSubarrays(int A[], int num,
                   int K, int size)
{
    // Store the indices
    // containing num
    vector<int> indices;
    for (int i = 0; i < size; i++) {
        if (A[i] == num)
            indices.push_back(i);
    }
 
    // If the occurrence of num
    // in the entire array
    // is less than K
    if (indices.size() < K)
 
        // No such subarrays are possible
        return 0;
 
    // Store the previous
    // index of num
    int prev = -1;
 
    // Store the count of
    // total subarrays
    int ans = 0;
 
    // Store the count of
    // subarrays for current
    // K occurrences
    int ctr = 0;
 
    for (int i = 0;
         i <= indices.size() - K;
         i++) {
 
        ctr = indices[i] - prev;
 
        if (i < indices.size() - K) {
 
            ctr *= (indices[i + K]
                    - indices[i + K - 1]);
        }
        else {
            ctr *= ((size - 1)
                    - indices[i + K - 1] + 1);
        }
 
        ans += ctr;
        prev = indices[i];
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 1, 5, 3, 5, 7, 5, 6,
                5, 10, 5, 12, 5 };
 
    int num = 5;
 
    int K = 3;
 
    int size = sizeof(A) / sizeof(int);
 
    cout << countSubarrays(A, num, K, size);
 
    return 0;
}

Java

// Java program to count subarrays
// which contains a given number
// exactly K times
 
import java.util.*;
public class Main {
 
    // Function to return
    // the count of subarrays
    // which contains given
    // number exactly K times
    public static int countSubarrays(
        int A[], int num,
        int K, int size)
    {
        // Store the indices
        // containing num
        ArrayList<Integer> indices
            = new ArrayList<Integer>();
 
        for (int i = 0; i < size; i++) {
            if (A[i] == num) {
                indices.add(i);
            }
        }
 
        if (indices.size() < K) {
            return 0;
        }
 
        // Store the previous
        // index of num
        int prev = -1;
 
        // Store the count of
        // total subarrays
        int ans = 0;
 
        // Store the count of
        // subarrays for current
        // K occurrences
        int ctr = 0;
 
        for (int i = 0;
             i <= indices.size() - K;
             i++) {
 
            ctr = indices.get(i) - prev;
 
            if (i < indices.size() - K) {
 
                ctr *= (indices.get(i + K)
                        - indices.get(i + K - 1));
            }
            else {
                ctr *= ((size - 1)
                        - indices.get(i + K - 1) + 1);
            }
 
            ans += ctr;
            prev = indices.get(i);
        }
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int A[] = { 1, 5, 3, 5, 7, 5,
                    6, 5, 10, 5, 12, 5 };
 
        int num = 5;
 
        int K = 3;
 
        int size = A.length;
 
        System.out.println(
            countSubarrays(A, num, K, size));
    }
}

Python3

# Python3 program to 
# count subarrays which 
# contains a given number
# exactly K times
 
# Function to return
# the count of subarrays
# which contains given
# number exactly K times
def countSubarrays(A, num,
                   K, size):
  # Store the indices
  # containing num
  indices = []
  for i in range (size):
    if (A[i] == num):
      indices.append(i)
       
  # If the occurrence of num
  # in the entire array
  # is less than K
  if (len(indices) < K):
     
    # No such subarrays are possible
    return 0
   
  # Store the previous
  # index of num
  prev = -1
 
  # Store the count of
  # total subarrays
  ans = 0
 
  # Store the count of
  # subarrays for current
  # K occurrences
  ctr = 0
   
  for i in range (len(indices) - K + 1):
    ctr = indices[i] - prev
    if (i < len(indices) - K):
      ctr *= (indices[i + K] -
              indices[i + K - 1])        
    else:
      ctr *= ((size - 1) -
               indices[i + K - 1] + 1)
    ans += ctr
    prev = indices[i]
  return ans
 
# Driver code
if __name__ == "__main__":
  A = [1, 5, 3, 5, 7, 5, 
       6, 5, 10, 5, 12, 5]
  num = 5
  K = 3
  size = len(A)
  print(countSubarrays(A, num, K, size))
     
# This code is contributed by Chitranayal

C#

// C# program to count subarrays
// which contains a given number
// exactly K times
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the count of subarrays
// which contains given number exactly K times
public static int countSubarrays(int[] A, int num,
                                 int K, int size)
{
     
    // Store the indices
    // containing num
    ArrayList indices = new ArrayList();
 
    for(int i = 0; i < size; i++) 
    {
        if (A[i] == num) 
        {
            indices.Add(i);
        }
    }
 
    if (indices.Count < K)
    {
        return 0;
    }
 
    // Store the previous
    // index of num
    int prev = -1;
 
    // Store the count of
    // total subarrays
    int ans = 0;
 
    // Store the count of
    // subarrays for current
    // K occurrences
    int ctr = 0;
 
    for(int i = 0; 
            i <= indices.Count - K;
            i++)
    {
        ctr = (int)indices[i] - prev;
        if (i < indices.Count - K)
        {
            ctr *= ((int)indices[i + K] - 
                    (int)indices[i + K - 1]);
        }
        else
        {
            ctr *= ((size - 1) - 
                    (int)indices[i + K - 1] + 1);
        }
        ans += ctr;
        prev = (int)indices[i];
    }
    return ans;
}
 
// Driver code
static public void Main()
{
    int[] A = { 1, 5, 3, 5, 7, 5, 
                6, 5, 10, 5, 12, 5 };
 
    int num = 5;
    int K = 3;
    int size = A.Length;
 
    Console.WriteLine(countSubarrays(A, num, K, size));
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// JavaScript program to count subarrays
// which contains a given number
// exactly K times
 
// Function to return the count of subarrays
// which contains given number exactly K times
function countSubarrays(A, num, K, size)
{
      
    // Store the indices
    // containing num
    let indices = [];
  
    for(let i = 0; i < size; i++)
    {
        if (A[i] == num)
        {
            indices.push(i);
        }
    }
  
    if (indices.length < K)
    {
        return 0;
    }
  
    // Store the previous
    // index of num
    let prev = -1;
  
    // Store the count of
    // total subarrays
    let ans = 0;
  
    // Store the count of
    // subarrays for current
    // K occurrences
    let ctr = 0;
  
    for(let i = 0;
            i <= indices.length - K;
            i++)
    {
        ctr = indices[i] - prev;
        if (i < indices.length - K)
        {
            ctr *= (indices[i + K] -
                    indices[i + K - 1]);
        }
        else
        {
            ctr *= ((size - 1) -
                    indices[i + K - 1] + 1);
        }
        ans += ctr;
        prev = indices[i];
    }
    return ans;
}
  
  // Driver Code
     
    let A = [ 1, 5, 3, 5, 7, 5,
                6, 5, 10, 5, 12, 5 ];
  
    let num = 5;
    let K = 3;
    let size = A.length;
  
    document.write(countSubarrays(A, num, K, size));
            
</script>

Output:

Time Complexity: O(N), where N is the size of the array.
Space Complexity: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!