Editorial for Series Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: David

Solution 1 - Using loop

This problem can be solved by storing each number in the series in an array in order. Then, for each query, loop over the array starting at the first index and stopping at the queried index, adding each element to an accumulator. This method is sufficient for passing the first subtask.
Example Java code:

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // Construct an array containing each number in the series.
    int[] series = new int[n];
    for (int i = 0; i < n; i++) {
      series[i] = sc.nextInt();
    }
    int k = sc.nextInt();
    for (int i = 0; i < k; i++) {
      int end = sc.nextInt();
      int sum = 0;
      // For each query, loop over the array until the specified index.
      for (int j = 0; j < end; j++) {
        sum += series[j];
      }
      System.out.println(sum);
    }
  }
}

Solution 2 - Prefix sum array

A more efficient approach would be a prefix sum array. Instead of storing each number in the series, instead keep track of the sum of the current number in the series plus the previous number in the array. This way, the $ith$ ~ith~ index of the array will be the sum of all numbers in the series between and including the first and $ith$ ~ith~ numbers. This method will pass the remaining cases.
Example Java code:

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] psa = new int[n + 1];
    psa[0] = 0;
    for (int i = 0; i < n; i++) {
      // For each number in the series, set the corresponding
      // index in the prefix sum array to itself plus the previous
      // index in the array. Note the first index is 0 to account
      // for the first number in the series.
      psa[i + 1] = sc.nextInt() + psa[i];
    }
    int k = sc.nextInt();
    for (int i = 0; i < k; i++) {
      // Simply query the appropriate array index to get the sum.
      System.out.println(psa[sc.nextInt()]);
    }
  }
}

Comments

There are no comments at the moment.