Sum of f(a[i], a[j]) over all pairs in an array of n integers

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

1. Firstly, iterate through all possible pairs using two nested loops.
2. 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

1. We multiply the number by the number of items that came before it as we move down the list.
2. 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.
3. 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.
4. 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

Run Code

Java Code

/* 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

Run Code

Input

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

Output

4

You can also read about the Longest Consecutive Sequence.

Complexities

Time complexity 

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.

Conclusion

In this article, we have found the sum of f(a[i], a[j]) over all pairs in an array of n integers. We hope that this blog will help you understand the concept of a hash table, and if you want to learn more about the hash table, check out our other blogs on the hashtable, hashtable vs stl map, the difference between hashmap and hashtable, and Hash Function in Data Structure.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!