CODEWITHSUNDEEP
javaarraysmatrixaddition
Sanjay Rao
Sanjay Rao

Reputation: 548

Efficient solution to add each of the element in the array with the other element

This looks very trivial and is not a home work question.

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=0;j<arr.length;j++)
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

This prints all the sum of each elements. This is O(n^2).

I want to know if this could be solved more efficiently.

Upvotes: 0

Views: 641

Answers (3)

edocetirwi
edocetirwi

Reputation: 548

Do you care about the order in which the results are printed out? If you don't maybe you can split the task and look at parallel reduction.

I've not tested it, but something in these lines

public void sum(int[] arr){
for(int i=0;i<arr.length;i++)
{
   for(int j=0;j<arr.length/2;j=+2)
   System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
   System.out.println(arr[i+1]+"+"+arr[j+1]+"+"+"="+(arr[i+1]+arr[j+1]));
}   
}//end of sum function

Upvotes: 0

Garrett Hall
Garrett Hall

Reputation: 30032

You can add matrices faster if you use sparse matrices. Since 0 + 0 = 0, a sparse matrix allows you to skip performing addition on those elements.

Otherwise, as others have said you can parrallelize the problem quite easily as well.

Upvotes: 0

esaj
esaj

Reputation: 16035

Since A + B is equal to B + A, you could just check the elements after the initial element in index i:

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=i;j<arr.length;j++) //Note: j = i, not j = 0
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

It's still O(n^2)/2, so the complexity is still basically quadratic.

Upvotes: 2

Related Questions