Count of subsequences having maximum distinct elements

0 0 4 minutes read

Given an arr of size n. The problem is to count all the subsequences having maximum number of distinct elements.

Examples:

Input : arr[] = {4, 7, 6, 7}
Output : 2
The indexes for the subsequences are:
{0, 1, 2} - Subsequence is {4, 7, 6} and
{0, 2, 3} - Subsequence is {4, 6, 7}

Input : arr[] = {9, 6, 4, 4, 5, 9, 6, 1, 2}
Output : 8

Naive Approach: Consider all the subsequences having distinct elements and count the one’s having maximum distinct elements.

Efficient Approach: Create a hash table to store the frequency of each element of the array. Take product of all the frequencies.
The solution is based on the fact that there is always 1 subsequence possible when all elements are distinct. If elements repeat, every occurrence of repeating element makes a mew subsequence of distinct elements.

Implementation:

C++

// C++ implementation to count subsequences having
// maximum distinct elements
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long int ull;
 
// function to count subsequences having
// maximum distinct elements
ull countSubseq(int arr[], int n)
{
    // unordered_map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
 
    ull count = 1;
 
    // count frequency of each element
    for (int i = 0; i < n; i++)
        um[arr[i]]++;
 
    // traverse 'um'
    for (auto itr = um.begin(); itr != um.end(); itr++)
 
        // multiply frequency of each element
        // and accumulate it in 'count'
        count *= (itr->second);
 
    // required number of subsequences
    return count;
}
 
// Driver program to test above
int main()
{
    int arr[] = { 4, 7, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Count = "
         << countSubseq(arr, n);
    return 0;
}

Java

// Java implementation to count subsequences having 
// maximum distinct elements
import java.util.HashMap;
 
class zambiatek
{
     
    // function to count subsequences having
    // maximum distinct elements
    public static long countSubseq(int[] arr, int n) 
    {
 
        // unordered_map 'um' implemented as
        // hash table
        HashMap<Integer, Integer> um = new HashMap<>();
 
        long count = 1;
 
        // count frequency of each element
        for (int i = 0; i < n; i++)
        {
            if (um.get(arr[i]) != null)
            {
                int a = um.get(arr[i]);
                um.put(arr[i], ++a);
            }
            else
                um.put(arr[i], 1);
        }
         
        // traverse 'um'
        for (HashMap.Entry<Integer, Integer> entry : um.entrySet())
        {
             
            // multiply frequency of each element
            // and accumulate it in 'count'
            count *= entry.getValue();
        }
         
        // required number of subsequences
        return count;
    }
 
    // Driver Code
    public static void main(String[] args) 
    {
        int[] arr = { 4, 7, 6, 7 };
        int n = arr.length;
        System.out.println("Count = " + countSubseq(arr, n));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python 3 implementation to count subsequences 
# having maximum distinct elements
 
# function to count subsequences having
# maximum distinct elements
def countSubseq(arr, n):
     
    # unordered_map 'um' implemented
    # as hash table
    # take range equal to maximum 
    # value of arr
    um = {i:0 for i in range(8)}
 
    count = 1
 
    # count frequency of each element
    for i in range(n):
        um[arr[i]] += 1
 
    # traverse 'um'
    for key, values in um.items():
         
        # multiply frequency of each element
        # and accumulate it in 'count'
        if(values > 0):
            count *= values
 
    # required number of subsequences
    return count
 
# Driver Code
if __name__ == '__main__':
    arr = [4, 7, 6, 7]
    n = len(arr)
    print("Count =", countSubseq(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation to count subsequences
// having maximum distinct elements
using System;
using System.Collections.Generic; 
     
class GFG
{
     
    // function to count subsequences having
    // maximum distinct elements
    public static long countSubseq(int[] arr,
                                   int n) 
    {
 
        // unordered_map 'um' implemented as
        // hash table
        Dictionary<int, 
                   int> um = new Dictionary<int,
                                            int>();
 
        long count = 1;
 
        // count frequency of each element
        for (int i = 0; i < n; i++)
        {
            if (um.ContainsKey(arr[i]))
            {
                int a = um[arr[i]];
                um.Remove(arr[i]);
                um.Add(arr[i], ++a);
            }
            else
                um.Add(arr[i], 1);
        }
         
        // traverse 'um'
        foreach(KeyValuePair<int, int> entry in um)
        {
             
            // multiply frequency of each element
            // and accumulate it in 'count'
            count *= entry.Value;
        }
         
        // required number of subsequences
        return count;
    }
 
    // Driver Code
    public static void Main(String[] args) 
    {
        int[] arr = { 4, 7, 6, 7 };
        int n = arr.Length;
        Console.WriteLine("Count = " + 
                           countSubseq(arr, n));
    }
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript implementation to count subsequences having
// maximum distinct elements
 
// function to count subsequences having
// maximum distinct elements
function countSubseq(arr, n)
{
 
    // unordered_map 'um' implemented as
    // hash table
    var um = new Map();
 
    var count = 1;
 
    // count frequency of each element
    for (var i = 0; i < n; i++)
    {
        if(um.has(arr[i]))
            um.set(arr[i], um.get(arr[i])+1)
        else
            um.set(arr[i], 1);
    }
 
    // traverse 'um'
    um.forEach((value, key) => {
         
        // multiply frequency of each element
        // and accumulate it in 'count'
        count *= value;
    });
     
    // required number of subsequences
    return count;
}
 
// Driver program to test above
var arr = [4, 7, 6, 7];
var n = arr.length;
document.write( "Count = "
      + countSubseq(arr, n));
 
// This code is contributed by noob2000.
</script>

Output:

Count = 2

Time Complexity: O(n).
Auxiliary Space: O(n).

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!