Cuente los subarreglos que tienen un solo elemento distinto que se puede obtener de un arreglo dado

Dada una array arr[] de tamaño N , la tarea es contar el número de subarreglos que consisten en un solo elemento distinto que se puede obtener de una array dada.

Ejemplos:

Entrada: N = 4, arr[] = { 2, 2, 2, 2 }
Salida: 7
Explicación: Todos esos subarreglos {{2}, {2}, {2}, {2}, {2, 2}, {2, 2, 2}, {2, 2, 2, 2}} . Por lo tanto, el recuento total de dichos subarreglos es 7.

Entrada: N = 3, arr[] = { 1, 1, 3 }
Salida: 4

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

• Inicialice un mapa para almacenar la frecuencia de los elementos de la array .
• Recorra la array y actualice la frecuencia de cada elemento en el Mapa.
• Recorra el mapa y verifique si la frecuencia del elemento actual es mayor que 1. 
   
• Si se encuentra que es cierto, entonces incremente el conteo de subarreglos por la frecuencia del elemento actual – 1 .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count subarrays of
// single distinct element into
// which given array can be split
void divisionalArrays(int arr[3], int N)
{
    // Stores the count
    int sum = N;
 
    // Stores frequency of
    // array elements
    unordered_map<int, int> mp;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        mp[arr[i]]++;
    }
 
    // Traverse the map
    for (auto x : mp) {
        if (x.second > 1) {
 
            // Increase count of
            // subarrays by (frequency-1)
            sum += x.second - 1;
        }
    }
    cout << sum << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 3 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
    divisionalArrays(arr, N);
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to count subarrays of
  // single distinct element into
  // which given array can be split
  static void divisionalArrays(int arr[], int N)
  {
 
    // Stores the count
    int sum = N;
 
    // Stores frequency of
    // array elements
    HashMap<Integer, Integer> mp
      = new HashMap<Integer, Integer>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
      if (mp.containsKey(arr[i]))
      {
        mp.put(arr[i], mp.get(arr[i]) + 1);
      }
      else
      {
        mp.put(arr[i], 1);
      }
    }
 
    // Traverse the map
    for (Map.Entry x : mp.entrySet())
    {
 
      if ((int)x.getValue() > 1)
      {
 
        // Increase count of
        // subarrays by (frequency-1)
        sum += (int)x.getValue() - 1;
      }
    }
 
    System.out.println(sum);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 1, 1, 3 };
    int N = arr.length;
    divisionalArrays(arr, N);
  }
}
 
// This code is contributed by Dharanendra L V

# python 3 program for the above approach
from collections import defaultdict
 
# Function to count subarrays of
# single distinct element into
# which given array can be split
def divisionalArrays(arr, N):
 
    # Stores the count
    sum = N
 
    # Stores frequency of
    # array elements
    mp = defaultdict(int)
 
    # Traverse the array
    for i in range(N):
        mp[arr[i]] += 1
 
    # Traverse the map
    for x in mp:
        if (mp[x] > 1):
 
            # Increase count of
            # subarrays by (frequency-1)
            sum += mp[x] - 1
    print(sum)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 1, 3]
    N = len(arr)
    divisionalArrays(arr, N)
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count subarrays of
// single distinct element into
// which given array can be split
static void divisionalArrays(int []arr, int N)
{
     
    // Stores the count
    int sum = N;
     
    // Stores frequency of
    // array elements
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
     
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
        if (mp.ContainsKey(arr[i]))
        {
            mp[arr[i]] =  mp[arr[i]] + 1;
        }
        else
        {
            mp.Add(arr[i], 1);
        }
    }
     
    // Traverse the map
    foreach(KeyValuePair<int, int> x in mp)
    {
        if ((int)x.Value > 1)
        {
             
            // Increase count of
            // subarrays by (frequency-1)
            sum += (int)x.Value - 1;
        }
    }
     
    Console.WriteLine(sum);
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 1, 3 };
    int N = arr.Length;
     
    divisionalArrays(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for the above approach
 
// Function to count subarrays of
// single distinct element into
// which given array can be split
function divisionalArrays(arr, N)
{
    // Stores the count
    var sum = N;
 
    // Stores frequency of
    // array elements
    var mp = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
        if(mp.has(arr[i]))
        {
            mp.set(arr[i], mp.get(arr[i])+1);
        }
        else
        {
            mp.set(arr[i],1);
        }
    }
 
    // Traverse the map
    mp.forEach((value, key) => {
        if (value > 1) {
 
            // Increase count of
            // subarrays by (frequency-1)
            sum += value - 1;
        }
    });
 
    document.write( sum);
}
 
// Driver Code
var arr =[1, 1, 3];
var N = arr.length;
divisionalArrays(arr, N);
 
</script>

4

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