Finding the sum of common elements between n number of arrays in java

Question

I have a program that sums the common elements of two arrays. For that I used two for loops and if I have three then I could use three for loops. But how to sum the common elements of n number of arrays where n is coming during run time.

I don't know how to change the number of loops during run time or is there any other relevant concept for this ?

Here is the code I've tried for summing twoarrays:

import java.util.Scanner;

public class Sample {
    public static void main(String... args)
    {
        Scanner sc=new Scanner(System.in);
        int arr1[]={1,2,3,4,5},arr2[]={4,5,6,7,8},sum=0;
        for (int i=0;i<arr1.length;i++)
        {
            for (int j=0;j<arr2.length;j++)
            {
                if (arr1[i]==arr2[j])
                {
                    sum+=(arr1[i]);
                }
            }
        }
    }
}

Answer 1

There can be different implementation for that. You can use the following approach. Here is the pseudo code

1. use a 2D array to store the array. if the number of array is n and size is m then the array will be input[n][m]
2. Use a ArrayList commonItems to store the common items of. Initiate it with the elements of input[0]
3. Now iterate through the array for i = 1 to n-1. compare with every input[i], store only the common items of commonItems and input[i] at each step. You can do it by converting the input[i] into a list and by using retainAll method.
4. At the end of the iteration the commonItem list will contains the common numbers only. Now sum the value of this list.

Answer 2

There is actually a more general method, that also answers the question "how to change the number of loops during run time?".

The general question

We are looking for a way to implement something equivalent to this:

for (i1 = 0; i1 < k1; i1++) { 
  for (i2 = 0; i2 < k2; i2++) {
    for (i3 = 0; i3 < k3; i3++) {
       ...
         for (in = 0; in < kn; in++) {
           f(x1[i1], x2[i2], ... xn[in]);
         }
       ...
     }
   }
 }

where, n is given at runtime and f is a function taking a list of n parameters, processing the current n-tuple.

A general solution

There is a general solution, based on the concept of recursion.

This is one implementation that produces the desired behavior:

void process(int idx, int n, int[][] x, int[] k, Object[] ntuple) {
    if (idx == n) {
        // we have a complete n-tuple, 
        // with an element from each of the n arrays
        f(ntuple);
        return;
    }

    // this is the idx'th "for" statement
    for (int i = 0; i < k[idx]; i++) {
        ntuple[idx] = x[idx][i];
        // with this recursive call we make sure that 
        // we also generate the rest of the for's
        process(idx + 1, n, x, k, ntuple);
    }
}

The function assumes that the n arrays are stored in a matrix x, and the first call should look like this:

process(0, n, x, k, new Object[n]);

Practical considerations

The solution above has a high complexity (it is O(k₁⋅k₂⋅..⋅k_n)), but sometimes it is possible to avoid going until the deepest loop.

Indeed, in the specific problem mentioned in this post (which requires summing common elements across all arrays), we can skip generating some tuples e.g. if already x₂[i₂] ≠ x₁[i₁].

In the recursive solution, those situations can easily be pruned. The specific code for this problem would probably look like this:

void process(int idx, int n, int[][] x, int[] k, int value) {
    if (idx == n) {
        // all elements from the current tuple are equal to "value". 
        // add this to the global "sum" variable
        sum += value;
        return;
    }

    for (int i = 0; i < k[idx]; i++) {
        if (idx == 0) {
            // this is the outer "for", set the new value
            value = x[0][i];
        } else {
            // check if the current element from the idx'th for
            // has the same value as all previous elements
            if (x[idx][i] == value) {
                process(idx + 1, n, x, k, value);
            }
        }
    }
}

Answer 3

Assuming that the index of the element is not important: a[1] = 2 and a[5] = 2, you only need two nested loops.

First you need to put n-1 arrays in a list of sets. Then loop over nth array and check if each element exists in all of the sets in the list. If it does exist then add to total.