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(N2) 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 (ith 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 timesint 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 codeint 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 timesimport 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 timesdef 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 codeif __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 timesusing System;using System.Collections;using System.Collections.Generic;class GFG{// Function to return the count of subarrays// which contains given number exactly K timespublic 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 codestatic 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 timesfunction 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:
14
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!