Conteo de subsecuencias que consisten en el mismo elemento

Dada una array A[] que consta de N enteros, la tarea es encontrar el número total de subsecuencias que contienen solo un número distinto repetido a lo largo de la subsecuencia.

Ejemplos:  

Entrada: A[] = {1, 2, 1, 5, 2} 
Salida: 7 
Explicación: 
Subsecuencias {1}, {2}, {1}, {5}, {2}, {1, 1} y { 2, 2} cumplen las condiciones requeridas.

Entrada: A[] = {5, 4, 4, 5, 10, 4} 
Salida: 11 
Explicación: 
Subsecuencias {5}, {4}, {4}, {5}, {10}, {4}, { 5, 5}, {4, 4}, {4, 4}, {4, 4} y {4, 4, 4} cumplen las condiciones requeridas. 

Enfoque: 
siga los pasos a continuación para resolver el problema: 

• Itere sobre la array y calcule la frecuencia de cada elemento en un HashMap .
• Atraviesa el HashMap. Para cada elemento, calcule el número de subsecuencias deseadas posibles por la ecuación:

 Número de subsecuencias posibles por arr[i] = 2 ^freq[arr[i]] – 1 

• Calcule el total de subsecuencias posibles de la array dada. 
   

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

<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

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N)