Dada una array arr[] de tamaño N , la tarea es contar el número de subarreglos de la array dada, de modo que cada elemento distinto en estos subarreglos aparezca al menos dos veces.
Ejemplos:
Entrada: arr[] = {1, 1, 2, 2, 2}
Salida: 6
Explicación: Los subarreglos en los que cada elemento aparece al menos dos veces son:{{1, 1}, {1, 1, 2, 2}, { 1, 1, 2, 2, 2}, {2, 2}, {2, 2, 2}, {2, 2}}.
Por lo tanto, la salida requerida es 6.Entrada: arr[] = {1, 2, 1, 2, 3}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y generar todos los subarreglos posibles de la array dada y, para cada subarreglo, verificar si todos los elementos en el subarreglo ocurren al menos dos veces o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente : Para optimizar el enfoque anterior, la idea es utilizar Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntSub para almacenar el recuento de subarreglos de modo que cada elemento del subarreglo aparezca al menos dos veces.
- Cree un Map , digamos cntFreq , para almacenar la frecuencia de los elementos de cada subarreglo.
- Inicialice una variable, digamos cntUnique , para almacenar el recuento de elementos en un subarreglo cuya frecuencia sea 1 .
- Atraviese el arreglo y genere todos los subarreglos posibles . Para cada subarreglo posible, almacene la frecuencia de cada elemento del arreglo y verifique si el valor de cntUnique es 0 o no. Si se encuentra que es cierto, incremente el valor de cntSub .
- Finalmente, imprima el valor de cntSub .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the count
// of subarrays having each
// element occurring at least twice
int cntSubarrays(int arr[], int N)
{
// Stores count of subarrays
// having each distinct element
// occurring at least twice
int cntSub = 0;
// Stores count of unique
// elements in a subarray
int cntUnique = 0;
// Store frequency of
// each element of a subarray
unordered_map<int, int> cntFreq;
// Traverse the given
// array
for (int i = 0; i < N;
i++) {
// Count frequency and
// check conditions for
// each subarray
for (int j = i; j < N;
j++) {
// Update frequency
cntFreq[arr[j]]++;
// Check if frequency of
// arr[j] equal to 1
if (cntFreq[arr[j]]
== 1) {
// Update Count of
// unique elements
cntUnique++;
}
else if (cntFreq[arr[j]]
== 2) {
// Update count of
// unique elements
cntUnique--;
}
// If each element of subarray
// occurs at least twice
if (cntUnique == 0) {
// Update cntSub
cntSub++;
}
}
// Remove all elements
// from the subarray
cntFreq.clear();
// Update cntUnique
cntUnique = 0;
}
return cntSub;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntSubarrays(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to get the count
// of subarrays having each
// element occurring at least twice
static int cntSubarrays(int arr[], int N)
{
// Stores count of subarrays
// having each distinct element
// occurring at least twice
int cntSub = 0;
// Stores count of unique
// elements in a subarray
int cntUnique = 0;
// Store frequency of
// each element of a subarray
Map<Integer,
Integer> cntFreq = new HashMap<Integer,
Integer>();
// Traverse the given
// array
for(int i = 0; i < N; i++)
{
// Count frequency and
// check conditions for
// each subarray
for(int j = i; j < N; j++)
{
// Update frequency
cntFreq.put(arr[j],
cntFreq.getOrDefault(
arr[j], 0) + 1);
// Check if frequency of
// arr[j] equal to 1
if (cntFreq.get(arr[j]) == 1)
{
// Update Count of
// unique elements
cntUnique++;
}
else if (cntFreq.get(arr[j]) == 2)
{
// Update count of
// unique elements
cntUnique--;
}
// If each element of subarray
// occurs at least twice
if (cntUnique == 0)
{
// Update cntSub
cntSub++;
}
}
// Remove all elements
// from the subarray
cntFreq.clear();
// Update cntUnique
cntUnique = 0;
}
return cntSub;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 1, 2, 2, 2 };
int N = arr.length;
System.out.println(cntSubarrays(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program to implement # the above approach from collections import defaultdict # Function to get the count # of subarrays having each # element occurring at least twice def cntSubarrays(arr, N): # Stores count of subarrays # having each distinct element # occurring at least twice cntSub = 0 # Stores count of unique # elements in a subarray cntUnique = 0 # Store frequency of # each element of a subarray cntFreq = defaultdict(lambda : 0) # Traverse the given # array for i in range(N): # Count frequency and # check conditions for # each subarray for j in range(i, N): # Update frequency cntFreq[arr[j]] += 1 # Check if frequency of # arr[j] equal to 1 if (cntFreq[arr[j]] == 1): # Update Count of # unique elements cntUnique += 1 elif (cntFreq[arr[j]] == 2): # Update count of # unique elements cntUnique -= 1 # If each element of subarray # occurs at least twice if (cntUnique == 0): # Update cntSub cntSub += 1 # Remove all elements # from the subarray cntFreq.clear() # Update cntUnique cntUnique = 0 return cntSub # Driver code if __name__ == '__main__': arr = [ 1, 1, 2, 2, 2 ] N = len(arr) print(cntSubarrays(arr, N)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to get the count
// of subarrays having each
// element occurring at least twice
static int cntSubarrays(int[] arr, int N)
{
// Stores count of subarrays
// having each distinct element
// occurring at least twice
int cntSub = 0;
// Stores count of unique
// elements in a subarray
int cntUnique = 0;
// Store frequency of
// each element of a subarray
Dictionary<int,
int> cntFreq = new Dictionary<int,
int>();
// Traverse the given
// array
for(int i = 0; i < N; i++)
{
// Count frequency and
// check conditions for
// each subarray
for(int j = i; j < N; j++)
{
// Update frequency
if (cntFreq.ContainsKey(arr[j]))
{
var val = cntFreq[arr[j]];
cntFreq.Remove(arr[j]);
cntFreq.Add(arr[j], val + 1);
}
else
{
cntFreq.Add(arr[j], 1);
}
// Check if frequency of
// arr[j] equal to 1
if (cntFreq[arr[j]] == 1)
{
// Update Count of
// unique elements
cntUnique++;
}
else if (cntFreq[arr[j]] == 2)
{
// Update count of
// unique elements
cntUnique--;
}
// If each element of subarray
// occurs at least twice
if (cntUnique == 0)
{
// Update cntSub
cntSub++;
}
}
// Remove all elements
// from the subarray
cntFreq.Clear();
// Update cntUnique
cntUnique = 0;
}
return cntSub;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 1, 2, 2, 2 };
int N = arr.Length;
Console.Write(cntSubarrays(arr, N));
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to get the count
// of subarrays having each
// element occurring at least twice
function cntSubarrays(arr, N)
{
// Stores count of subarrays
// having each distinct element
// occurring at least twice
var cntSub = 0;
// Stores count of unique
// elements in a subarray
var cntUnique = 0;
// Store frequency of
// each element of a subarray
var cntFreq = new Map();
// Traverse the given
// array
for (var i = 0; i < N;
i++) {
// Count frequency and
// check conditions for
// each subarray
for (var j = i; j < N;
j++) {
// Update frequency
if(cntFreq.has(arr[j]))
cntFreq.set(arr[j], cntFreq.get(arr[j])+1)
else
cntFreq.set(arr[j], 1);
// Check if frequency of
// arr[j] equal to 1
if (cntFreq.get(arr[j])
== 1) {
// Update Count of
// unique elements
cntUnique++;
}
else if (cntFreq.get(arr[j])
== 2) {
// Update count of
// unique elements
cntUnique--;
}
// If each element of subarray
// occurs at least twice
if (cntUnique == 0) {
// Update cntSub
cntSub++;
}
}
// Remove all elements
// from the subarray
cntFreq = new Map();
// Update cntUnique
cntUnique = 0;
}
return cntSub;
}
// Driver Code
var arr = [1, 1, 2, 2, 2];
var N = arr.length;
document.write( cntSubarrays(arr, N));
// This code is contributed by itsok.
</script>
Producción:
6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)