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

Question

I have a program that summarizes the common elements of two arrays. For this, I used two for loops, and if I have three, I could use three for loops. But how to sum the common elements n of the number of arrays, where n comes at runtime.

I don’t know how to change the number of cycles at runtime, or is there another suitable concept for this?

Here is the code I tried to sum two angles:

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

In fact, there is a more general method that also answers the question "how to change the number of cycles at runtime?".

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 specified at runtime, and f is a function that takes a list of n parameters, processing the current n-tuple.

Common decision

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

This is one implementation that creates 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 the matrix x , and the first call should look like this:

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

Practical considerations

The solution above has high complexity (this is O (k ₁ ⋅k ₂ ⋅..⋅k _n )), but sometimes you can avoid going to the deepest loop.

In fact, in the specific task mentioned in this article (which requires the summation of common elements across all arrays), we can skip the creation of some sets, for example. if already x ₂ [i ₂ ] ≠ x ₁ [i ₁ ].

In a recursive solution, these situations can be easily trimmed. The specific code for this problem is likely to 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 2

There may be another implementation for this. You can use the following approach. Here is the pseudo code

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

Answer 3

Assuming 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 the n-1 arrays in the list of sets. Then collapse the nth array and check if every element in all sets in the list exists. If it exists, add it to the total.