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 elementsvoid 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 codeint 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 codeif __name__ == "__main__": v = [1, 1, 1, 3, 3, 3] # Function Call distSubs(v) |
C#
// C# implementation of the above approachusing 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 codeconst v = [1, 1, 1, 3, 3, 3];// Function calldistSubsv); |
Output
Total subsequences with all elements distinct are : 15
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
