In the article, we are going to discuss one of the popular questions that is to find the sum of f(arr[i], arr[j]) over all pairs in an array of n integers.

Problem Statement

Suppose you have been given an array of N integers. You need to find the sum of differences of arr[j] and arr[i] such that they satisfy the below condition:

1<=i<j<=n

The difference between the two elements arr[j] and arr[i] canâ€™t be 0, 1, -1.

Example

Input

arr[] = {1, 2, 3, 1, 3}

Output

4

Pair (1, 3) and (1, 3) to give 2 each. Other pairs give 0 implies 4.

Brute Force Approach

Firstly, iterate through all possible pairs using two nested loops.

Check if the difference between the two elements will not be equal to 0, 1, -1 and sum up all such conditions.

Algorithm using the hash table

We multiply the number by the number of items that came before it as we move down the list.

To get the sum of the differences between all pairs that can be made using that number, subtract this result from the pre-sum of the number that comes before that number.

Deduct the count of occurrence of (number-1) and (number+1) from the previously calculated sum to eliminate those pairings whose absolute difference is =1.

Here, we add the count of (number+1) since the negative has already been added to the pre-computed sum of all pairs and deduct the count of (number-1) from the computed sum because it had previously been contributed to the sum.

C++ Code

/* C++ implementation to calculate the sum of f(a[i], a[j]) */
#include <bits/stdc++.h>
using namespace std;
/* function to calculate the sum of the required condition */
int sum(int a[], int n){
/* creating map to keep track of an occurrences */
unordered_map<int, int> map;
/* Count the number of times that a[i] can be in a pair by iterating through the list from beginning to finish; then, subtract pre sum to obtain the difference. */
int ans = 0, pre_sum = 0;
for (int i = 0; i < n; i++) {
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
if (map[a[i] - 1])
ans -= map[a[i] - 1];
if (map[a[i] + 1])
ans += map[a[i] + 1];
map[a[i]]++;
}
return ans;
}
/* Main program */
int main()
{
/* Input array */
int arr[] = { 1, 2, 3, 1, 3 };
/* Size of an input array */
int n = sizeof(arr) / sizeof(arr[0]);
/* Printing required output */
cout << sum(arr, n);
return 0;
}

You can also try this code with Online C++ Compiler

/* Java implementation to calculate the sum of f(a[i], a[j]) */
import java.util.*;
public class Main {
/* function to calculate the sum of the required condition */
public static int sum(int a[], int n)
{
/* creating map to keep track of an occurrences */
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
/* Count the number of times that a[i] can be in a pair by iterating through the list from beginning to finish; then, subtract pre sum to obtain the difference. */
int ans = 0, pre_sum = 0;
for (int i = 0; i < n; i++) {
ans += (i * a[i]) - pre_sum;
pre_sum += a[i];
if (map.containsKey(a[i] - 1))
ans -= map.get(a[i] - 1);
if (map.containsKey(a[i] + 1))
ans += map.get(a[i] + 1);
if(map.containsKey(a[i])) {
map.put(a[i], map.get(a[i]) + 1);
}
else {
map.put(a[i], 1);
}
}
return ans;
}
/* Main program */
public static void main(String args[])
{
/* Input array */
int a[] = { 1, 2, 3, 1, 3 };
/* Size of an input array */
int n = a.length;
/* Printing required output */
System.out.println(sum(a, n));
}
}

You can also try this code with Online Java Compiler

O(n), where n is the size of an array Reason: This method requires traversing the array once so that the time complexity will be O(n).

Space complexity

O(n), where n is the size of an array Reason: Required an O(n) space to store on the map.

Frequently Asked Questions

What do you mean by HashTable?

A hash table associates various keys with various values. Hash table implements the map, the serializable, and cloneable interfaces and inherits the dictionary type.

How come hash tables are quick?

The linear time complexity of O(n) is required when searching through an array-like data structure that is the search time grows linearly in proportion to the size of the data structure. Simply, searching through an array is slower than using a hash table.

What is the time complexity of a hash table?

No matter how many entries are in the table, hash tables typically offer constant-time O(1) lookup. The majority of hash table schemes have an O(n) worst-case lookup time.

What are the hash table's three fundamental operations?

The fundamental principle operations of a hash table are: search which searches for an element in the hash table, Insert which adds a new element to the hash table, and Delete which removes an element from the hash table.

What is the load factor of a hash table?

Load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.