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 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);
            }
        }
    }
}