CODEWITHSUNDEEP
java
NaMo
NaMo

Reputation: 533

Sum of contiguous subarrays of an array in least time

This is my code:

long sum(int[] arr) {
    long sum=0;
    int j,k;
    long sumtoadd;
    for (int i = 0; i < arr.length; i++)
    {
        for (j = i; j < arr.length; j++)
        {
            sumtoadd = 0;
            for (k = i; k <= j; k++)
            {
                sumtoadd = sumtoadd + arr[k];
            }
            sum = sumtoadd + sum;
        }
    }
    return sum;
}

Example:

Array : {1,2,3} Output: 20

Array : {1,1,1} Output: 10

I am trying to find the sum of all contiguous subarrays of an array, but for some of the cases, time is exceeding. This solution is working for all cases except large sized cases. Is there any better solution for this?

Upvotes: 1

Views: 244

Answers (2)

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

Instead of three nested loops, the answer can be found in one loop over the N array elements.

Reasoning:

If a given array element A[i] occurs in K subarrays, then it contributes its value to K subarrays, meaning it contributes K-times its value to the total sum. Now the element A[i] occurs in all subarrays with a start from 0 to i (inclusive), and an end from i+1 to N (inclusive), so K = (i+1)*(N-i).

Summary: every A[i] contributes (i+1)*(N-i)*A[i]. Do that in a single loop, and you're finished.

Upvotes: 0

yvs
yvs

Reputation: 517

public class Test1 {

static long sum2(int[] arr) {
    long n = arr.length;
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += (n-i)*(i+1)*arr[i];
    }
    return sum;
}

static int[] arr1 = new int[]{1,2,3,4,5,6,7,8,9};
static int[] arr2 = new int[]{1,1,1,1};

public static void main(String[] args) {
    System.out.println("sum(arr1) = " + sum(arr1));
    System.out.println("sum2(arr1) = " + sum2(arr1));
    System.out.println("sum(arr2) = " + sum(arr2));
    System.out.println("sum2(arr2) = " + sum2(arr2));
}

//your code to check
static long sum(int[] arr) {
    long sum=0;
    int j,k;
    long sumtoadd;
    for (int i = 0; i < arr.length; i++)
    {
        for (j = i; j < arr.length; j++)
        {
            sumtoadd = 0;
            for (k = i; k <= j; k++)
            {
                sumtoadd = sumtoadd + arr[k];
            }
            sum = sumtoadd + sum;
        }
    }
    return sum;
}

}

Upvotes: 3

Related Questions