Horje
Count of Subsequences with distinct elements

Given an array arr[] (1<=a[i]<=1e9) containing N (1<=N<=1e5) elements, the task is to find the total number of subsequences such that all elements in that subsequences are distinct. Since the answer can be very large print and modulo 1e9+7.

Examples:

Input: arr[] = [1, 1, 2, 2]
Output: 8
Explanation: The subsequences are [1], [1], [2], [2], [1, 2], [1, 2], [1, 2], [1, 2]

Input: arr[] = [1, 3, 2, 2]
Output: 11
Explanation: The subsequences are [1], [3], [2], [2], [1, 3], [1, 2], [1, 2], [3, 2], [3, 2], [1, 3, 2], [1, 3, 2]

Approach: To solve the problem follow the below idea:

This problem can be solved using unordered_map.

Follow the steps to solve the problem:

  • First, let’s store the frequency of all elements in a map
  • Suppose an element has a frequency of x then we have to either choose one element from this or exclude this element.
  • Remember we need all distinct elements so we can’t choose more than 1 same element.
  • So for an element with frequency x, we have (x+1) options (1 for excluding the elements)
  • Now for counting the number of subsequences, we can multiply the options that we have.
  • At last, we need to subtract 1 because one empty subsequence is generated so to exclude that we need to subtract 1.

Below is the code for the above approach:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
 
// Function to calculate subsequences with
// distinct elements
void distSubs(vector<int> v, int n)
{
    long long ans = 1;
 
    // Creating a map
    unordered_map<int, int> m;
 
    // Calculating frequency of each element
    for (int i = 0; i < n; i++) {
        m[v[i]]++;
    }
 
    // Calculating ans
    for (auto it : m) {
 
        ans = (ans % mod * (it.second + 1) % mod) % mod;
    }
 
    ans = (ans - 1 + mod) % mod;
 
    cout << "Total subsequences with all elements distinct "
            "are : "
         << ans << endl;
}
 
// Drivers code
int main()
{
 
    vector<int> v = { 1, 1, 1, 3, 3, 3 };
    int n = v.size();
 
    // Function Call
    distSubs(v, n);
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
 
public class DistinctSubsequences {
 
    private static final int MOD = 1000000007;
 
    // Function to calculate subsequences with distinct elements
    private static void distSubs(int[] arr, int n) {
        long ans = 1;
 
        // Creating a map to store element frequencies
        Map<Integer, Integer> frequencyMap = new HashMap<>();
 
        // Calculating frequency of each element
        for (int i = 0; i < n; i++) {
            frequencyMap.put(arr[i], frequencyMap.getOrDefault(arr[i], 0) + 1);
        }
 
        // Calculating ans
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int elementFrequency = entry.getValue();
            ans = (ans % MOD * (elementFrequency + 1) % MOD) % MOD;
        }
 
        ans = (ans - 1 + MOD) % MOD;
 
        System.out.println("Total subsequences with all elements distinct are: " + ans);
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 3, 3, 3};
        int n = arr.length;
 
        // Function Call
        distSubs(arr, n);
    }
}

Python3

def distSubs(v):
    mod = 10**9 + 7
    ans = 1
 
    # Creating a dictionary
    m = {}
 
    # Calculating frequency of each element
    for i in range(len(v)):
        m[v[i]] = m.get(v[i], 0) + 1
 
    # Calculating ans
    for key, value in m.items():
        ans = (ans % mod * (value + 1) % mod) % mod
 
    ans = (ans - 1 + mod) % mod
 
    print("Total subsequences with all elements distinct are:", ans)
 
# Drivers code
if __name__ == "__main__":
    v = [1, 1, 1, 3, 3, 3]
 
    # Function Call
    distSubs(v)

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
public class DistinctSubsequences
{
    private const int MOD = 1000000007;
 
    // Function to calculate subsequences with distinct elements
    private static void DistSubs(int[] arr, int n)
    {
        long ans = 1;
 
        // Creating a dictionary to store element frequencies
        Dictionary<int, int> frequencyMap = new Dictionary<int, int>();
 
        // Calculating frequency of each element
        for (int i = 0; i < n; i++)
        {
            if (frequencyMap.ContainsKey(arr[i]))
            {
                frequencyMap[arr[i]]++;
            }
            else
            {
                frequencyMap[arr[i]] = 1;
            }
        }
 
        // Calculating ans
        foreach (KeyValuePair<int, int> entry in frequencyMap)
        {
            int elementFrequency = entry.Value;
            ans = (ans % MOD * (elementFrequency + 1) % MOD) % MOD;
        }
 
        ans = (ans - 1 + MOD) % MOD;
 
        Console.WriteLine("Total subsequences with all elements distinct are: " + ans);
    }
 
    public static void Main(string[] args)
    {
        int[] arr = { 1, 1, 1, 3, 3, 3 };
        int n = arr.Length;
 
        // Function Call
        DistSubs(arr, n);
    }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Javascript

function distSubs(v) {
    const mod = 1e9 + 7;
    let ans = 1;
    // Creating a map
    const map = new Map();
    // Calculating frequency of each element
    for (let i = 0; i < v.length; i++) {
        if (map.has(v[i])) {
            map.set(v[i], map.get(v[i]) + 1);
        } else {
            map.set(v[i], 1);
        }
    }
    // Calculating ans
    for (const [key, value] of map) {
        ans = (ans % mod * (value + 1) % mod) % mod;
    }
    ans = (ans - 1 + mod) % mod;
    console.log("Total subsequences with all elements distinct are:", ans);
}
// Driver code
const v = [1, 1, 1, 3, 3, 3];
// Function call
distSubsv);

Output

Total subsequences with all elements distinct are : 15

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


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Sequence Transformation by Cyclic Shifting Sequence Transformation by Cyclic Shifting
Equation satisfiability check Equation satisfiability check
Efficient waste bagging Efficient waste bagging
Birthday Gift: Counting integer Arrays with interesting properties Birthday Gift: Counting integer Arrays with interesting properties
Check whether the frequency of the elements in the Array is unique or not Check whether the frequency of the elements in the Array is unique or not

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje