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 elementsull 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 aboveint 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 elementsimport java.util.HashMap;class neveropen{ // 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 elementsdef 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 Codeif __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 elementsusing 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 elementsfunction 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 abovevar 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).
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!
… [Trackback]
[…] Here you will find 74129 more Info on that Topic: geeksforgeeks.org/count-of-subsequences-having-maximum-distinct-elements/ […]
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/count-of-subsequences-having-maximum-distinct-elements/ […]