Count of subsequences consisting of the same element

0 0 3 minutes read

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] = 2^freq[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>

Output:

Time Complexity: O(NlogN)
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 zambiatek!