Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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]);
                }
            }
        }
    }
}
like image 866
Bharat Avatar asked Apr 10 '17 15:04

Bharat


People also ask

How do you find the common element between two arrays?

By using the retainAll() method of the HashSet we can find the common elements between two arrays.

How do you sum two arrays in Java?

You cannot use the plus operator to add two arrays in Java e.g. if you have two int arrays a1 and a2, doing a3 = a1 + a2 will give a compile-time error. The only way to add two arrays in Java is to iterate over them and add individual elements and store them into a new array.


3 Answers

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.
like image 154
stinepike Avatar answered Oct 20 '22 01:10

stinepike


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(k1⋅k2⋅..⋅kn)), 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 x2[i2] ≠ x1[i1].

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);
            }
        }
    }
}
like image 1
qwertyman Avatar answered Oct 20 '22 01:10

qwertyman


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.

like image 1
efekctive Avatar answered Oct 20 '22 01:10

efekctive