current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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]
share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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? –  Abdul Jul 29 at 12:33
    
I have edited the answer.is it clear now? –  aa1992 Jul 29 at 12:43
    
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. –  Abdul Jul 29 at 12:45
    
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/… –  aa1992 Jul 29 at 12:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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