Dada una array A de tamaño N donde los elementos de la array contienen valores de 1 a N con duplicados, la tarea es encontrar el número total de subarreglos que comienzan y terminan con el mismo elemento.
Ejemplos:
Entrada: A[] = {1, 2, 1, 5, 2}
Salida: 7
Explicación:
El total de 7 subconjuntos del conjunto dado son {1}, {2}, {1}, {5}, {2 }, {1, 2, 1} y {2, 1, 5, 2} comienzan y terminan con el mismo elemento.
Entrada: A[] = {1, 5, 6, 1, 9, 5, 8, 10, 8, 9}
Salida: 14
Explicación:
Total 14 subarreglo {1}, {5}, {6}, { 1}, {9}, {5}, {8}, {10}, {8}, {9}, {1, 5, 6, 1}, {5, 6, 1, 9, 5}, { 9, 5, 8, 10, 8, 9} y {8, 10, 8} comienzan y terminan con el mismo elemento.
Enfoque ingenuo: para cada elemento en la array, si también está presente en un índice diferente, aumentaremos nuestro resultado en 1. Además, todos los subarreglos de tamaño 1 son parte de los contados en el resultado. Por lo tanto, agregue N al resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Count total sub-array
// which start and end with same element
#include <bits/stdc++.h>
using namespace std;
// Function to find total sub-array
// which start and end with same element
void cntArray(int A[], int N)
{
// initialize result with 0
int result = 0;
for (int i = 0; i < N; i++) {
// all size 1 sub-array
// is part of our result
result++;
// element at current index
int current_value = A[i];
for (int j = i + 1; j < N; j++) {
// Check if A[j] = A[i]
// increase result by 1
if (A[j] == current_value) {
result++;
}
}
}
// print the result
cout << result << endl;
}
// Driver code
int main()
{
int A[] = { 1, 5, 6, 1, 9,
5, 8, 10, 8, 9 };
int N = sizeof(A) / sizeof(int);
cntArray(A, N);
return 0;
}
Java
// Java program to Count total sub-array
// which start and end with same element
public class Main {
// function to find total sub-array
// which start and end with same element
public static void cntArray(int A[], int N)
{
// initialize result with 0
int result = 0;
for (int i = 0; i < N; i++) {
// all size 1 sub-array
// is part of our result
result++;
// element at current index
int current_value = A[i];
for (int j = i + 1; j < N; j++) {
// Check if A[j] = A[i]
// increase result by 1
if (A[j] == current_value) {
result++;
}
}
}
// print the result
System.out.println(result);
}
// Driver code
public static void main(String[] args)
{
int[] A = { 1, 5, 6, 1, 9,
5, 8, 10, 8, 9 };
int N = A.length;
cntArray(A, N);
}
}
Python3
# Python3 program to count total sub-array
# which start and end with same element
# Function to find total sub-array
# which start and end with same element
def cntArray(A, N):
# Initialize result with 0
result = 0
for i in range(0, N):
# All size 1 sub-array
# is part of our result
result = result + 1
# Element at current index
current_value = A[i]
for j in range(i + 1, N):
# Check if A[j] = A[i]
# increase result by 1
if (A[j] == current_value):
result = result + 1
# Print the result
print(result)
print("\n")
# Driver code
A = [ 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 ]
N = len(A)
cntArray(A, N)
# This code is contributed by PratikBasu
C#
// C# program to Count total sub-array
// which start and end with same element
using System;
class GFG{
// function to find total sub-array
// which start and end with same element
public static void cntArray(int []A, int N)
{
// initialize result with 0
int result = 0;
for (int i = 0; i < N; i++)
{
// all size 1 sub-array
// is part of our result
result++;
// element at current index
int current_value = A[i];
for (int j = i + 1; j < N; j++)
{
// Check if A[j] = A[i]
// increase result by 1
if (A[j] == current_value)
{
result++;
}
}
}
// print the result
Console.Write(result);
}
// Driver code
public static void Main()
{
int[] A = { 1, 5, 6, 1, 9,
5, 8, 10, 8, 9 };
int N = A.Length;
cntArray(A, N);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to Count total sub-array
// which start and end with same element
// Function to find total sub-array
// which start and end with same element
function cntArray(A, N)
{
// initialize result with 0
var result = 0;
for (var i = 0; i < N; i++) {
// all size 1 sub-array
// is part of our result
result++;
// element at current index
var current_value = A[i];
for (var j = i + 1; j < N; j++) {
// Check if A[j] = A[i]
// increase result by 1
if (A[j] == current_value) {
result++;
}
}
}
// print the result
document.write( result );
}
// Driver code
var A = [1, 5, 6, 1, 9,
5, 8, 10, 8, 9];
var N = A.length;
cntArray(A, N);
// This code is contributed by noob2000.
</script>
14
Complejidad de tiempo: O(N 2 ) , donde N es el tamaño de la array
Complejidad de espacio: O(1)
Enfoque eficiente: podemos optimizar el método anterior al observar que la respuesta solo depende de las frecuencias de los números en la array original.
Por ejemplo , en el arreglo {1, 5, 6, 1, 9, 5, 8, 10, 8, 9}, la frecuencia de 1 es 2 y el subarreglo que contribuye a la respuesta es {1}, {1} y {1, 5, 6, 1} respectivamente, es decir, un total de 3.
Por lo tanto, calcule la frecuencia de cada elemento en la array. Luego, para cada elemento, el incremento de la cuenta por el resultado producido por la siguiente fórmula:
((frecuencia del elemento)*(frecuencia del elemento + 1)) / 2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Count total sub-array
// which start and end with same element
#include <bits/stdc++.h>
using namespace std;
// function to find total sub-array
// which start and end with same element
void cntArray(int A[], int N)
{
// initialize result with 0
int result = 0;
// array to count frequency of 1 to N
int frequency[N + 1] = { 0 };
for (int i = 0; i < N; i++) {
// update frequency of A[i]
frequency[A[i]]++;
}
for (int i = 1; i <= N; i++) {
int frequency_of_i = frequency[i];
// update result with sub-array
// contributed by number i
result += +((frequency_of_i)
* (frequency_of_i + 1))
/ 2;
}
// print the result
cout << result << endl;
}
// Driver code
int main()
{
int A[] = { 1, 5, 6, 1, 9, 5,
8, 10, 8, 9 };
int N = sizeof(A) / sizeof(int);
cntArray(A, N);
return 0;
}
Java
// Java program to Count total sub-array
// which start and end with same element
public class Main {
// function to find total sub-array which
// start and end with same element
public static void cntArray(int A[], int N)
{
// initialize result with 0
int result = 0;
// array to count frequency of 1 to N
int[] frequency = new int[N + 1];
for (int i = 0; i < N; i++) {
// update frequency of A[i]
frequency[A[i]]++;
}
for (int i = 1; i <= N; i++) {
int frequency_of_i = frequency[i];
// update result with sub-array
// contributed by number i
result += ((frequency_of_i)
* (frequency_of_i + 1))
/ 2;
}
// print the result
System.out.println(result);
}
// Driver code
public static void main(String[] args)
{
int[] A = { 1, 5, 6, 1, 9, 5,
8, 10, 8, 9 };
int N = A.length;
cntArray(A, N);
}
}
Python3
# Python3 program to count total sub-array
# which start and end with same element
# Function to find total sub-array
# which start and end with same element
def cntArray(A, N):
# Initialize result with 0
result = 0
# Array to count frequency of 1 to N
frequency = [0] * (N + 1)
for i in range(0, N):
# Update frequency of A[i]
frequency[A[i]] = frequency[A[i]] + 1
for i in range(1, N + 1):
frequency_of_i = frequency[i]
# Update result with sub-array
# contributed by number i
result = result + ((frequency_of_i) *
(frequency_of_i + 1)) / 2
# Print the result
print(int(result))
print("\n")
# Driver code
A = [ 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 ]
N = len(A)
cntArray(A, N)
# This code is contributed by PratikBasu
C#
// C# program to Count total sub-array
// which start and end with same element
using System;
class GFG{
// function to find total sub-array which
// start and end with same element
public static void cntArray(int []A, int N)
{
// initialize result with 0
int result = 0;
// array to count frequency of 1 to N
int[] frequency = new int[N + 1];
for (int i = 0; i < N; i++)
{
// update frequency of A[i]
frequency[A[i]]++;
}
for (int i = 1; i <= N; i++)
{
int frequency_of_i = frequency[i];
// update result with sub-array
// contributed by number i
result += ((frequency_of_i) *
(frequency_of_i + 1)) / 2;
}
// print the result
Console.Write(result);
}
// Driver code
public static void Main()
{
int[] A = { 1, 5, 6, 1, 9, 5,
8, 10, 8, 9 };
int N = A.Length;
cntArray(A, N);
}
}
// This code is contributed by Nidhi_Biet
Javascript
<script>
// Javascript program to Count total sub-array
// which start and end with same element
// function to find total sub-array which
// start and end with same element
function cntArray(A, N)
{
// initialize result with 0
let result = 0;
// array to count frequency of 1 to N
let frequency = Array.from({length: N+1}, (_, i) => 0);
for (let i = 0; i < N; i++) {
// update frequency of A[i]
frequency[A[i]]++;
}
for (let i = 1; i <= N; i++) {
let frequency_of_i = frequency[i];
// update result with sub-array
// contributed by number i
result += ((frequency_of_i)
* (frequency_of_i + 1))
/ 2;
}
// print the result
document.write(result);
}
// Driver Code
let A = [ 1, 5, 6, 1, 9, 5,
8, 10, 8, 9 ];
let N = A.length;
cntArray(A, N);
</script>
14
Complejidad de tiempo: O(N) , donde N es el tamaño de la array
Complejidad de espacio: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por divyeshrabadiya07 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA