Dada una array arr[] , la tarea es calcular el recuento de posibles tripletas de modo que puedan eliminarse de la array sin cambiar la media aritmética de la array.
Ejemplo:
Entrada: arr[] = {8, 7, 4, 6, 3, 0, 7}
Salida: 3
Explicación: La array dada tiene 3 tripletas posibles, de modo que eliminarlas no afectará la media aritmética de la array. Hay {7, 3, 0}, {4, 6, 0} y {3, 0, 7}.Entrada: arr[] = {5, 5, 5, 5}
Salida: 4
Enfoque: El problema dado se puede resolver usando la observación de que para que la media de la array restante sea constante, la media del triplete eliminado debe ser igual a la media de la array inicial. Por lo tanto, el problema dado se reduce a encontrar el conteo de trillizos con la suma dada que se puede resolver usando hash siguiendo los pasos a continuación:
- Itere la array dada arr[] para todos los valores posibles de pares (a, b) e inserte su suma en un mapa .
- Mientras itera la array, verifique si ( TargetSum – (a + b) ) ya existe en el mapa. En caso afirmativo, aumente el valor del conteo requerido por su frecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// triplets with the given sum
int countTriplets(int arr[], int n, int sum)
{
// Stores the final count
int cnt = 0;
// Map to store occurred elements
unordered_map<int, int> m;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if Sum - (a + b)
// is present in map
int k = sum - (arr[i] + arr[j]);
if (m.find(k) != m.end())
// Increment count
cnt += m[k];
}
// Store the occurrences
m[arr[i]]++;
}
// Return Answer
return cnt;
}
// Function to C=find count of triplets
// that can be removed without changing
// arithmetic mean of the given array
int count_triplets(int arr[], int n)
{
// Stores sum of all elements
// of the given array
int sum = 0;
// Calculate the sum of the array
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
// Store the arithmetic mean
int mean = sum / n;
int reqSum = 3 * mean;
if ((3 * sum) % n != 0)
return 0;
// Return count
return countTriplets(arr, n, reqSum);
}
// Driver Code
int main()
{
int arr[] = { 5, 5, 5, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << count_triplets(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.util.HashMap;
class GFG {
// Function to count the number of
// triplets with the given sum
static int countTriplets(int[] arr, int n, int sum)
{
// Stores the final count
int cnt = 0;
// Map to store occurred elements
HashMap<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if Sum - (a + b)
// is present in map
int k = sum - (arr[i] + arr[j]);
if (m.containsKey(k))
// Increment count
cnt += m.get(k);
}
// Store the occurrences
if (m.containsKey(arr[i]))
m.put(arr[i],m.get(arr[i])+1);
else
m.put(arr[i],1);
}
// Return Answer
return cnt;
}
// Function to C=find count of triplets
// that can be removed without changing
// arithmetic mean of the given array
static int count_triplets(int[] arr, int n)
{
// Stores sum of all elements
// of the given array
int sum = 0;
// Calculate the sum of the array
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
// Store the arithmetic mean
int mean = sum / n;
int reqSum = 3 * mean;
if ((3 * sum) % n != 0)
return 0;
// Return count
return countTriplets(arr, n, reqSum);
}
// Driver Code
public static void main (String[] args)
{
int[] arr = { 5, 5, 5, 5 };
int N = arr.length;
System.out.println(count_triplets(arr, N));
}
}
// This code is contributed by Shubham Singh.
Python3
# python code for the above approach
# Function to count the number of
# triplets with the given sum
def countTriplets(arr, n, sum):
# Stores the final count
cnt = 0
# Map to store occurred elements
m = {}
for i in range(0, n-1):
for j in range(i+1, n):
# Check if Sum - (a + b)
# is present in map
k = sum - (arr[i] + arr[j])
if (k in m):
# Increment count
cnt += m[k]
# Store the occurrences
if arr[i] in m:
m[arr[i]] += 1
else:
m[arr[i]] = 1
# Return Answer
return cnt
# Function to C=find count of triplets
# that can be removed without changing
# arithmetic mean of the given array
def count_triplets(arr, n):
# Stores sum of all elements
# of the given array
sum = 0
# Calculate the sum of the array
for i in range(0, n):
sum = sum + arr[i]
# Store the arithmetic mean
mean = sum // n
reqSum = 3 * mean
if ((3 * sum) % n != 0):
return 0
# Return count
return countTriplets(arr, n, reqSum)
# Driver Code
if __name__ == "__main__":
arr = [5, 5, 5, 5]
N = len(arr)
print(count_triplets(arr, N))
# This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count the number of
// triplets with the given sum
static int countTriplets(int[] arr, int n, int sum)
{
// Stores the final count
int cnt = 0;
// Map to store occurred elements
Dictionary<int, int> m = new Dictionary<int, int>();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if Sum - (a + b)
// is present in map
int k = sum - (arr[i] + arr[j]);
if (m.ContainsKey(k))
// Increment count
cnt += m[k];
}
// Store the occurrences
if (m.ContainsKey(arr[i]))
m[arr[i]]++;
else
m[arr[i]] = 1;
}
// Return Answer
return cnt;
}
// Function to C=find count of triplets
// that can be removed without changing
// arithmetic mean of the given array
static int count_triplets(int[] arr, int n)
{
// Stores sum of all elements
// of the given array
int sum = 0;
// Calculate the sum of the array
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
// Store the arithmetic mean
int mean = sum / n;
int reqSum = 3 * mean;
if ((3 * sum) % n != 0)
return 0;
// Return count
return countTriplets(arr, n, reqSum);
}
// Driver Code
public static void Main()
{
int[] arr = { 5, 5, 5, 5 };
int N = arr.Length;
Console.WriteLine(count_triplets(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to count the number of
// triplets with the given sum
const countTriplets = (arr, n, sum) => {
// Stores the final count
let cnt = 0;
// Map to store occurred elements
let m = {};
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
// Check if Sum - (a + b)
// is present in map
let k = sum - (arr[i] + arr[j]);
if (k in m)
// Increment count
cnt += m[k];
}
// Store the occurrences
if (arr[i] in m) m[arr[i]]++;
else m[arr[i]] = 1;
}
// Return Answer
return cnt;
}
// Function to C=find count of triplets
// that can be removed without changing
// arithmetic mean of the given array
const count_triplets = (arr, n) => {
// Stores sum of all elements
// of the given array
let sum = 0;
// Calculate the sum of the array
for (let i = 0; i < n; i++) {
sum = sum + arr[i];
}
// Store the arithmetic mean
let mean = parseInt(sum / n);
let reqSum = 3 * mean;
if ((3 * sum) % n != 0)
return 0;
// Return count
return countTriplets(arr, n, reqSum);
}
// Driver Code
let arr = [5, 5, 5, 5];
let N = arr.length;
document.write(count_triplets(arr, N));
// This code is contributed by rakeshsahni
</script>
Producción:
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA