4
\$\begingroup\$

I have an array of some arbitrary int values; I want to find the array containing the sum of the past elements in the current index.

Example:

int[] myArray = new int[5]{ 5, 7, 8, 2, 6 };

I would attempt to:

  • myArray[0] = 5
  • myArray[1] = myArray[0] + myArray[currentIndex] = 5 + 7
  • myArray[2] = 5 + 12 + 8 and so forth till my finished array is:
  • [5, 12, 25, 44, 92]

I have 2 solutions, one in Java 7, and the other in Java 8, and I was wondering if it was possible to get critiqued on both of them, specifically on how to make the code more terse and efficient i.e. cutting out unnecessary steps or operations.

Java 7 (or language agnostic) solution:

public static int[] sumifyIn7(int[] array) {
    int length = array.length;
    for(int i = 1; i < length; i++) {
        int sumSoFar = 0;
        for(int j = 0; j <= i; j ++) {
            sumSoFar += array[j];
        }
        array[i] = sumSoFar;
    }
    return array;
}

Side-note: Am I correct in saying this solution is \$O(nlog(n))\$?

Java 8 solution:

I'm very unfamiliar with Java 8, and plan on getting up to date with it during the school year, but this is what I could put together, but I'm sure it could be improved based on how redundant it seems.

public static int[] sumifyIn8(int[] array) {
    int length = array.length;
    for (int i = 1; i < length; i++) {
        array[i] = Arrays.stream(Arrays.copyOfRange(array, 0, i + 1)).sum();
    }
    return array;
}

Test:

public static void main(String[] args) {
    System.out.println(Arrays.toString(sumifyIn8(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 })));
    System.out.println(Arrays.toString(sumifyIn7(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 })));
}

Test Results:

[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]

[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Am I correct in saying this solution is O(nlog(n))?

Proof

Whenever there are nested loops,the complexity is measured by number of times inner most loop get executed. Example

for (i = 1; i <=n; i ++) {
   for (j = 1; j <=i; j ++) {
      // some O(1) expressions
}

inner loop executed=1+2+3+4+...n=(n*(n+1))/2≈ n2.
Hence time complexity is O(n2).

In your case the inner loop is executed 2+3+4+..+n times≈n2.

Hence time complexity of your solution is O(n2)

Your first approach in Java 7 can be improved by eliminating the inner loop.
Here is an approach which uses only one loop.

    array[1]=array[0]+array[1];
    int sum=array[0];
    int length=array.length;
    for(int i=2;i<length;i++)
    {
        array[i]+=array[i-1]+sum;
        sum+=array[i-1];//storing the sum up to i-1;
    }

Improvement

  • Eliminated the inner loop.

  • Added a new variable sum which keeps the summation of the numbers up to index i-2 when calculating array[i].

  • Time Complexity reduced from O(n2) to O(n).

Hope this helps.

\$\endgroup\$
4
  • \$\begingroup\$ Is the int length = array.length; and referring to the variable, instead of having to check the length of the array every single iteration improvement negligible? \$\endgroup\$ Jul 29, 2015 at 12:33
  • \$\begingroup\$ I have edited the answer.is it clear now? \$\endgroup\$
    – aakansha
    Jul 29, 2015 at 12:43
  • \$\begingroup\$ oh, I wasn't critiquing your answer. I was genuinely curious as to whether it was negligible, as I've been doing it since my data structures course, as it made sense, but have never actually found out if it was of substantial improvement. \$\endgroup\$ Jul 29, 2015 at 12:45
  • \$\begingroup\$ A call to array.length is a O(1) operation or a constant operation as length is a public final member of array.So its almost equivalent to accessing a local variable.check this for more detail stackoverflow.com/questions/1208320/… \$\endgroup\$
    – aakansha
    Jul 29, 2015 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.