Java Coding Test Course, Finding Range Sum 3

Hello! Today, we will solve a Java coding test problem titled ‘Finding the Interval Sum 3’. The goal of this problem is to devise an algorithm that efficiently computes the sum of a specific interval in a given array. Let’s take a look at the problem.

Problem Description

Given an integer array A and m queries, each query is represented by two integers X and Y, and the task is to output the value of A[X] + A[X+1] + ... + A[Y]. Note that the queries are 1-indexed.

Input Format

  • The first line contains two integers N (the number of elements in the array) and M (the number of queries).
  • The second line contains an array A consisting of N integers.
  • From the third line onward, each of the M lines contains two integers X and Y representing each query.

Output Format

Print the result of each query on a new line.

Example

Input Example:
5 3
1 2 3 4 5
1 3
2 4
1 5

Output Example:
6
9
15

Approach to the Problem

To find the sum of a specific interval in a 1-indexed array, we can use the following method:

  1. First, create a sum array: Pre-calculate the sum of the original array and create an array that stores the sum at each index. Using this sum array allows us to calculate the interval sum in O(1) time complexity.
  2. Calculate the interval sum: The total sum of the interval can be computed as sum[Y] - sum[X-1]. Here, sum[i] is the sum from 1 to i in the input array.

Algorithm Implementation

Now, let’s implement the algorithm in Java. Below is the actual code:

import java.util.Scanner;

public class IntervalSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Get the size of the array N and number of queries M
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        // Declare array A and input values
        long[] A = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = scanner.nextLong();
        }

        // Declare sum array
        long[] sum = new long[N + 1];

        // Create sum array
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + A[i];
        }

        // Process queries
        for (int j = 0; j < M; j++) {
            int X = scanner.nextInt();
            int Y = scanner.nextInt();
            // Calculate and output the interval sum
            System.out.println(sum[Y] - sum[X - 1]);
        }

        // Close the scanner
        scanner.close();
    }
}

Code Explanation

The above code is structured as follows:

  1. It uses Scanner to receive input. It reads the size of the array (N) and the number of queries (M).
  2. It creates the array A and assigns values in a 1-indexed manner.
  3. It generates the sum array sum. This array stores the sum from 1 to i of the array A.
  4. It reads each query’s X and Y, calculates the interval sum, and prints the result.

Time Complexity Analysis

The time complexity of this algorithm is as follows:

  • It takes O(N) time to create the sum array.
  • It takes O(1) time to process each query. Therefore, for M queries, it takes O(M) time.

In conclusion, the overall time complexity of the algorithm is O(N + M). This is an efficient way to solve the problem.

Conclusion

Today, we learned how to solve an algorithm problem in Java through the ‘Finding the Interval Sum 3’ problem. I hope you understand how to enhance query efficiency by utilizing the sum array. Try more practice problems for additional experience. We will meet again in the next lesson on a different topic. Thank you!