How to add elements before a specific element in an array using only one for loop if possible in java

Viewed 196

new to coding and just wondering if this is possible. If I had an array of (1,1,1,2,3) and a separate empty array where im going to put my output, is it possible using only one for loop to make each element add all elements before it. So the output would be something like this (1,2,3,5,8). So it would be (1, 1+1, 1+1+1, 1+1+1+2, 1+1+1+2+3). I've been able to do it using two for loops but can't figure out a way to do it with just one. Thanks in advance for any help.

7 Answers

There is already a method which you can use if you don't want to implement it yourself:

int[] nums = {1, 1, 1, 2, 3};
Arrays.parallelPrefix(nums,Integer::sum);
System.out.println(Arrays.toString(nums));

//[1, 2, 3, 5, 8]

This is useful if you also need to do other calculations than making cumulative sum. For example if you want to multiply the elements instead of adding them:

int[] nums = {1, 2, 3, 4, 5};
Arrays.parallelPrefix(nums, (i,j) -> i*j);
System.out.println(Arrays.toString(nums));

//[1, 2, 6, 24, 120]

From the doc Arrays.parallelPrefix for parallelPrefix(int[] array, IntBinaryOperator op) which accepts an int array (there are also overloaded methods for long[], double[] ...)

Cumulates, in parallel, each element of the given array in place, using the supplied function. For example if the array initially holds [2, 1, 0, 3] and the operation performs addition, then upon return the array holds [2, 3, 3, 6]. Parallel prefix computation is usually more efficient than sequential loops for large arrays.

A one-pass version, which does an in-place modification to the array by keeping the running total in sum, assigning it immediately back to the current element of the array:

int sum = 0;
for (int i = 0; i < arr.length; i++) {
    arr[i] = sum += arr[i];
}

See live demo.

Here's a single pass solution that leaves the original array untouched.

int[] nums = {1, 1, 1, 2, 3};
int[] output = new int[nums.length];
int accumulator = 0;  // This will be the sum of all previous indices
for (int i = 0; i < nums.length; i++) {
  output[i] = nums[i] + accumulator;  // Since output starts at 0, add both the current value of nums and the accumulated sum.
  accumulator += nums[i];
}
System.out.println(Arrays.toString(output));

You can first set the first element of the output array to the first element of the original array. Then, each next output is the sum of the previous output and the current array value.

int[] output = new int[arr.length];
output[0] = arr[0];
for(int i = 1; i < arr.length; i++) output[i] = output[i - 1] + arr[i];

You can modify the array in-place like so:

for(int i = 1; i < arr.length; i++) arr[i] += arr[i - 1];

A solution with an extra array to store the result is provided. Also, an in-place update to the input array is also provided.

    int[] input = { 1, 1, 1, 2, 3 };
    int[] output = new int[input.length];

    
    // a new output array is created leaving the input untouched
    output[0] = input[0];
    
    
    for (int i = 1; i < input.length; i++) {
        output[i] = output[i - 1] + input[i];
    }

    System.out.println(Arrays.toString(output));
    
    
    // the input array is updated inplace
    for (int i = 1; i < input.length; i++) {
        input[i] = output[i - 1] + input[i];
    }
    
    System.out.println(Arrays.toString(input));

Practice this question on leetcode : https://leetcode.com/problems/running-sum-of-1d-array/

int nums[] = {1,1,1,2,3}; // initialize your array
int newNums[] = new int[nums.length]; // initialize new array
newNums[0] = nums[0]; // the below for loop starts from 1-st position. hence copy the zero index element in the new array
for(int i = 1; i < nums.length; i++){
    newNums[i] = newNums[i - 1] + nums[i]; // calculate sum and store in new array
}

Solution using Java Stream API

You can do it in a single statement using Java Stream API:

int[] result = arr.length >= 2
                ? Stream.iterate(
                            new int[] { arr[0], arr[1] }, 
                            temp -> new int[] { temp[1], temp[0] + temp[1] }
                        )
                        .mapToInt(temp -> temp[1])
                        .limit(arr.length)
                        .toArray()
                : arr;

Explanation

  1. Here we are limiting the infinite sequential ordered Stream returned by Stream#iterate with the help of Stream#limit.
  2. We are using new int[] { arr[0], arr[1] } as the seed where arr is your given array.
  3. The UnaryOperator is preparing a new int[] for the next iteration.

Note that this solution keeps your given array, arr undisturbed.

DEMO

Related