Dada una array de n enteros, encuentra la suma de f(a[i], a[j]) de todos los pares (i, j) tales que (1 <= i < j <= n).
f(a[i], a[j]):
If |a[j]-a[i]| > 1 f(a[i], a[j]) = a[j] - a[i] Else // if |a[j]-a[i]| <= 1 f(a[i], a[j]) = 0
Ejemplos:
Input : 6 6 4 4 Output : -8 Explanation: All pairs are: (6 - 6) + (6 - 6) + (6 - 6) + (4 - 6) + (4 - 6) + (4 - 6) + (4 - 6) + (4 - 4) + (4 - 4) = -8 Input: 1 2 3 1 3 Output: 4 Explanation: the pairs that add up are: (3, 1), (3, 1) to give 4, rest all pairs according to condition gives 0.
Un enfoque ingenuo es iterar a través de todos los pares y calcular f(a[i], a[j]), y resumirlo mientras se atraviesan dos bucles anidados nos dará nuestra respuesta.
Complejidad del tiempo: O(n^2)
Un enfoque eficiente sería usar una función map/hash para mantener un conteo de cada número que aparece y luego recorrer la lista. Mientras recorremos la lista, multiplicamos la cantidad de números que están antes y el número en sí. Luego reste este resultado con la suma previa del número anterior a ese número para obtener la suma de la diferencia de todos los pares posibles con ese número. Para eliminar todos los pares cuya diferencia absoluta sea <=1, simplemente reste el recuento de ocurrencias de (número-1) y (número+1) de la suma calculada previamente. Aquí restamos el conteo de (número 1) de la suma calculada como se había agregado previamente a la suma, y sumamos el conteo de (número + 1) ya que el negativo se agregó a la suma precalculada de todos los pares. .
Complejidad de tiempo: O(n)
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to calculate the
// sum of f(a[i], aj])
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum
int sum(int a[], int n)
{
// map to keep a count of occurrences
unordered_map<int, int> cnt;
// Traverse in the list from start to end
// number of times a[i] can be in a pair and
// to get the difference we subtract pre_sum.
int ans = 0, pre_sum = 0;
for (int i = 0; i < n; i++) {
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
// if the (a[i]-1) is present then
// subtract that value as f(a[i], a[i]-1)=0
if (cnt[a[i] - 1])
ans -= cnt[a[i] - 1];
// if the (a[i]+1) is present then
// add that value as f(a[i], a[i]-1)=0
// here we add as a[i]-(a[i]-1)<0 which would
// have been added as negative sum, so we add
// to remove this pair from the sum value
if (cnt[a[i] + 1])
ans += cnt[a[i] + 1];
// keeping a counter for every element
cnt[a[i]]++;
}
return ans;
}
// Driver code
int main()
{
int a[] = { 1, 2, 3, 1, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << sum(a, n);
return 0;
}
Java
// Java program to calculate
// the sum of f(a[i], aj])
import java.util.*;
public class GfG {
// Function to calculate the sum
public static int sum(int a[], int n)
{
// Map to keep a count of occurrences
Map<Integer,Integer> cnt = new HashMap<Integer,Integer>();
// Traverse in the list from start to end
// number of times a[i] can be in a pair and
// to get the difference we subtract pre_sum
int ans = 0, pre_sum = 0;
for (int i = 0; i < n; i++) {
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
// If the (a[i]-1) is present then subtract
// that value as f(a[i], a[i]-1) = 0
if (cnt.containsKey(a[i] - 1))
ans -= cnt.get(a[i] - 1);
// If the (a[i]+1) is present then
// add that value as f(a[i], a[i]-1)=0
// here we add as a[i]-(a[i]-1)<0 which would
// have been added as negative sum, so we add
// to remove this pair from the sum value
if (cnt.containsKey(a[i] + 1))
ans += cnt.get(a[i] + 1);
// keeping a counter for every element
if(cnt.containsKey(a[i])) {
cnt.put(a[i], cnt.get(a[i]) + 1);
}
else {
cnt.put(a[i], 1);
}
}
return ans;
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 2, 3, 1, 3 };
int n = a.length;
System.out.println(sum(a, n));
}
}
// This code is contributed by Swetank Modi
Python3
# Python3 program to calculate the # sum of f(a[i], aj]) # Function to calculate the sum def sum(a, n): # map to keep a count of occurrences cnt = dict() # Traverse in the list from start to end # number of times a[i] can be in a pair and # to get the difference we subtract pre_sum. ans = 0 pre_sum = 0 for i in range(n): ans += (i * a[i]) - pre_sum pre_sum += a[i] # if the (a[i]-1) is present then # subtract that value as f(a[i], a[i]-1)=0 if (a[i] - 1) in cnt: ans -= cnt[a[i] - 1] # if the (a[i]+1) is present then add that # value as f(a[i], a[i]-1)=0 here we add # as a[i]-(a[i]-1)<0 which would have been # added as negative sum, so we add to remove # this pair from the sum value if (a[i] + 1) in cnt: ans += cnt[a[i] + 1] # keeping a counter for every element if a[i] not in cnt: cnt[a[i]] = 0 cnt[a[i]] += 1 return ans # Driver Code if __name__ == '__main__': a = [1, 2, 3, 1, 3] n = len(a) print(sum(a, n)) # This code is contributed by # SHUBHAMSINGH10
C#
using System;
using System.Collections.Generic;
// C# program to calculate
// the sum of f(a[i], aj])
public class GfG
{
// Function to calculate the sum
public static int sum(int[] a, int n)
{
// Map to keep a count of occurrences
IDictionary<int, int> cnt = new Dictionary<int, int>();
// Traverse in the list from start to end
// number of times a[i] can be in a pair and
// to get the difference we subtract pre_sum
int ans = 0, pre_sum = 0;
for (int i = 0; i < n; i++)
{
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
// If the (a[i]-1) is present then subtract
// that value as f(a[i], a[i]-1) = 0
if (cnt.ContainsKey(a[i] - 1))
{
ans -= cnt[a[i] - 1];
}
// If the (a[i]+1) is present then
// add that value as f(a[i], a[i]-1)=0
// here we add as a[i]-(a[i]-1)<0 which would
// have been added as negative sum, so we add
// to remove this pair from the sum value
if (cnt.ContainsKey(a[i] + 1))
{
ans += cnt[a[i] + 1];
}
// keeping a counter for every element
if (cnt.ContainsKey(a[i]))
{
cnt[a[i]] = cnt[a[i]] + 1;
}
else
{
cnt[a[i]] = 1;
}
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
int[] a = new int[] {1, 2, 3, 1, 3};
int n = a.Length;
Console.WriteLine(sum(a, n));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to calculate the
// sum of f(a[i], aj])
// Function to calculate the sum
function sum(a, n)
{
// map to keep a count of occurrences
var cnt = new Map();
// Traverse in the list from start to end
// number of times a[i] can be in a pair and
// to get the difference we subtract pre_sum.
var ans = 0, pre_sum = 0;
for (var i = 0; i < n; i++) {
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
// if the (a[i]-1) is present then
// subtract that value as f(a[i], a[i]-1)=0
if (cnt.has(a[i] - 1))
ans -= cnt.get(a[i] - 1);
// if the (a[i]+1) is present then
// add that value as f(a[i], a[i]-1)=0
// here we add as a[i]-(a[i]-1)<0 which would
// have been added as negative sum, so we add
// to remove this pair from the sum value
if(cnt.has(a[i] + 1))
ans += cnt.get(a[i] + 1);
// keeping a counter for every element
if(cnt.has(a[i]))
cnt.set(a[i], cnt.get(a[i])+1)
else
cnt.set(a[i], 1)
}
return ans;
}
// Driver code
var a = [1, 2, 3, 1, 3];
var n = a.length;
document.write( sum(a, n));
</script>
Producción:
4
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)