Sunday, September 25, 2022
HomeSoftware DevelopmentCount subarrays having at least X distinct elements that occur exactly Y...

Count subarrays having at least X distinct elements that occur exactly Y times

[ad_1]

Given three integers N, X, Y, and an array arr[] of size N, the task is to find the count of subarrays having at least X distinct elements that occur only Y times.

Example:

Input: N = 9, X = 2, Y = 2, arr[] = {2, 1, 2, 5, 3, 1, 3, 2, 5}
Output:10
Explanation:
Subarrays with at least X distinct elements occurring exactly Y times are: 
{2, 1, 2, 5, 3, 1}, {2, 1, 2, 5, 3, 1, 3}, {2, 1, 2, 5, 3, 1, 3, 2}, {2, 1, 2, 5, 3, 1, 3, 2, 5},  
{1, 2, 5, 3, 1, 3}, {1, 2, 5, 3, 1, 3, 2}, {1, 2, 5, 3, 1, 3, 2, 5}, {2, 5, 3, 1, 3, 2},  
{2, 5, 3, 1, 3, 2, 5}, {5, 3, 1, 3, 2, 5}

Input: N = 3, X = 1, Y = 2, arr[] = {1, 3, 5}
Output: 0
Explanation: No element is occurring twice in the given array

 

Naive Approach: The idea is to generate all possible subarrays of the given array and traverse over the generated subarrays to find the frequency of all distinct elements. Then check whether there are at least X distinct elements that occur only Y times in the subarray. If found, increment the result and return the final result.

Time Complexity: O(N3)
Auxiliary Space: O(N)

Efficient Approach: The problem can also be solved in an efficient way based on the following idea:

Keep track of the frequency of elements while generating the subarray and count of unique elements with exactly Y occurrences in that subarray with the help of hashing. In this way, there is no need to build all the subarrays and check them afterward.

Follow the steps below to implement the above idea:

  • Iterate from i = 0 to N – 1:
    • Declare a hash map (say cntFreq) to store the frequency of the distinct elements in the subarray.
    • Initialize a variable (say cntDistinct) to store the number of distinct elements that occur exactly Y times in the subarray.
    • Iterate using a nested loop from j = i to N to consider all the subarrays:
      • Increment the frequency of arr[j].
      • If the frequency is Y then increment cntDistinct.
      • If frequency exceeds Y and becomes Y+1, decrement cntDistinct,
    • If the subarray has at least X distinct elements satisfying the condition then increase the count of subarrays fulfilling the condition.
  • Finally, return the count of the subarrays.

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int countSubarray(int arr[], int X, int Y, int N)

{

    

    

    int cntSub = 0;

  

    for (int i = 0; i < N; i++) {

        int cntDistinct = 0;

  

        

        unordered_map<int, int> cntFreq;

        for (int j = i; j < N; j++) {

  

            

            

            cntFreq[arr[j]]++;

            if (cntFreq[arr[j]] == Y) {

                cntDistinct++;

            }

            else if (cntFreq[arr[j]] == Y + 1) {

  

                

                

                

                cntDistinct--;

            }

  

            

            

            if (cntDistinct >= X) {

                cntSub++;

            }

        }

    }

  

    

    return cntSub;

}

  

int main()

{

    int N = 9, X = 2, Y = 2;

    int arr[] = { 2, 1, 2, 5, 3, 1, 3, 2, 5 };

  

    

    cout << countSubarray(arr, X, Y, N);

    return 0;

}

Time Complexity: O(N2)
Auxiliary Space: O(N)

[ad_2]

Source link

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments