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

Difficulty Level Easy
Frequently asked in Cisco Facebook Hike Publicis Sapient
Array Hash MathViews 2369

The problem statement asks to find out the Sum of f(a[i], a[j]) over all pairs in an array of n integers in such a way that 1 < = i < j < = n considering that we are provided an array of integers.

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

Example

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

Explanation

Only pair 3,1 and 3,1 pairs.

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

Explanation

Here also, two pairs of (1, 3) are there.

Algorithm

  1. Declare a map and set the output to 0 and checksum to 0.
  2. Traverse the array starting from i=0 to i=n,
    1. Do output += (i * a[i]) – checksum and checksum += a[i];
    2. Check if a[i]-1 is present as a key in the map.
      1. If true, then update output by adding the value of a[i]-1 of the map into the output.
      2. Check if a[i]+1 is present as a key in the map. If true, then update output by adding the value of a[i]+1 of the map into the output.
    3. If none of the condition satisfies, then simply count and store the frequency of array element into the map.
  3. Return output.

Explanation

We got an array integer, our task is to find out the sum of all of the pairs present in an array that satisfies the above condition. If none of the pairs satisfy the given condition then simply we return 0. To solve this we will use a Map and simultaneously doing all the operations on each array element and updating our output and checking on our Map as well. We are going to take an extra variable that maintains an eye on our real output, we can call it as a checksum. We will set output and checksum to 0. And that’s how we find sum of f(a[i], a[j]) over all pairs in an array of n integers.

Let us consider an example:

Example

Arr[]={1, 2, 3, 1, 3} , Output: 0, Checksum:0

  • We will pick 0th index element and then perform and then multiplying by its index, and subtracting checksum and then add that into the output, we got

Output: 0, Checksum: 1

map {1=1}, any condition doesn’t satisfy, so we add the value into the map.

  • For 1st index element, do the same operation, but this time, it will satisfy the condition of the first if statement, and after getting the updated output, we get.

Updated Output: 0, Checksum: 3

map {1=1, 2=1}, this time also we add that value with its occurrence into the map.

  • For 2nd element, same operation done as before, this time it finds the element a[i]-1 and we got updated output:

Updated Output: 2, Checksum: 6

map {1=1, 2=1, 3=1}, adding up the element and its frequency.

  • For 3rd element, it satisfies the second if statement, means it follows if the map contains the value a[i]+1, then after we got the updated output:

Updated Output: 0, Checksum: 7, map: {1=2, 2=1, 3=1}

  • For the 4th element, after passing the first if statement.

Updated Output: 4, Checksum: 10

map {1=2, 2=1, 3=2}

And we will return the Output: 4

Code

C++ code to find sum of f(a[i], a[j]) over all pairs in an array of n integers

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}

4

Java code to find sum of f(a[i], a[j]) over all pairs in an array of n integers

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}

4

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. The usage of HashMap allows us to perform searching/deletion/insertion in O(1). Thus the time complexity for finding the sum of f(a[i], a[j]) over all pairs in an array of n integers is reduced to linear.

Space Complexity

O(n) where “n” is the number of elements in the array. Since we may have to insert n keys in the HashMap, thus the space complexity is linear.

Translate »