Given an array A[] consisting of N integers, the task is to find the total number of subsequence which contain only one distinct number repeated throughout the subsequence.
Examples:
Input: A[] = {1, 2, 1, 5, 2}
Output: 7
Explanation:
Subsequences {1}, {2}, {1}, {5}, {2}, {1, 1} and {2, 2} satisfy the required conditions.Input: A[] = {5, 4, 4, 5, 10, 4}
Output: 11
Explanation:
Subsequences {5}, {4}, {4}, {5}, {10}, {4}, {5, 5}, {4, 4}, {4, 4}, {4, 4} and {4, 4, 4} satisfy the required conditions.
Approach:
Follow the steps below to solve the problem:
- Iterate over the array and calculate the frequency of each element in a HashMap.
- Traverse the HashMap. For each element, calculate the number of desired subsequences possible by the equation:
Number of subsequences possible by arr[i] = 2freq[arr[i]] – 1
- Calculate the total possible subsequences from the given array.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count subsequences in // array containing same element void CountSubSequence( int A[], int N) { // Stores the count // of subsequences int result = 0; // Stores the frequency // of array elements map< int , int > mp; for ( int i = 0; i < N; i++) { // Update frequency of A[i] mp[A[i]]++; } for ( auto it : mp) { // Calculate number of subsequences result = result + pow (2, it.second) - 1; } // Print the result cout << result << endl; } // Driver code int main() { int A[] = { 5, 4, 4, 5, 10, 4 }; int N = sizeof (A) / sizeof (A[0]); CountSubSequence(A, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to count subsequences in // array containing same element static void CountSubSequence( int A[], int N) { // Stores the count // of subsequences int result = 0 ; // Stores the frequency // of array elements Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < N; i++) { // Update frequency of A[i] mp.put(A[i], mp.getOrDefault(A[i], 0 ) + 1 ); } for (Integer it : mp.values()) { // Calculate number of subsequences result = result + ( int )Math.pow( 2 , it) - 1 ; } // Print the result System.out.println(result); } // Driver code public static void main(String[] args) { int A[] = { 5 , 4 , 4 , 5 , 10 , 4 }; int N = A.length; CountSubSequence(A, N); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to count subsequences in # array containing same element def CountSubSequence(A, N): # Stores the frequency # of array elements mp = {} for element in A: if element in mp: mp[element] + = 1 else : mp[element] = 1 result = 0 for key, value in mp.items(): # Calculate number of subsequences result + = pow ( 2 , value) - 1 # Print the result print (result) # Driver code A = [ 5 , 4 , 4 , 5 , 10 , 4 ] N = len (A) CountSubSequence(A, N) # This code is contributed by jojo9911 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to count subsequences in // array containing same element public static void CountSubSequence( int []A, int N) { // Stores the count // of subsequences int result = 0; // Stores the frequency // of array elements var mp = new Dictionary< int , int >(); for ( int i = 0; i < N; i++) { // Update frequency of A[i] if (mp.ContainsKey(A[i])) mp[A[i]] += 1; else mp.Add(A[i], 1); } foreach ( var it in mp) { // Calculate number of subsequences result = result + ( int )Math.Pow(2, it.Value) - 1; } // Print the result Console.Write(result); } // Driver code public static void Main() { int []A = { 5, 4, 4, 5, 10, 4 }; int N = A.Length; CountSubSequence(A, N); } } // This code is contributed by grand_master |
Javascript
<script> // Javascript program to implement // the above approach // Function to count subsequences in // array containing same element function CountSubSequence(A, N) { // Stores the count // of subsequences var result = 0; // Stores the frequency // of array elements var mp = new Map(); for ( var i = 0; i < N; i++) { // Update frequency of A[i] if (mp.has(A[i])) mp.set(A[i], mp.get(A[i])+1) else mp.set(A[i], 1) } mp.forEach((value, key) => { // Calculate number of subsequences result = result + Math.pow(2, value) - 1; }); // Print the result document.write( result ); } // Driver code var A = [5, 4, 4, 5, 10, 4]; var N = A.length; CountSubSequence(A, N); // This code is contributed by itsok. </script> |
11
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!