Java Coding Test Course, Range Sum

Hello! In this post, we will discuss the range sum problem for coding test preparation using Java. The range sum problem is one where we efficiently calculate the sum of elements in a specific range of a given array, and it is a common type of question in algorithm problems.

Problem Description

Given an array A, there are Q queries. Each query consists of two integers L and R, which represent the indices of the array A. For each query, compute the range sum from index L to index R.

Input

    The first line contains the size of the array N and the number of queries Q.
    The second line contains N integers A[1], A[2], ..., A[N].
    Following that, Q lines are given with L and R separated by space.

Output

    Print the range sum for each query, one per line.

Example Input

    5 3
    1 2 3 4 5
    1 3
    2 4
    1 5

Example Output

    6
    9
    15

Problem Solving Strategy

There are various ways to handle the range sum problem, but an inefficient way is to directly loop through and calculate the range sum for each query. In this case, the worst-case time complexity could be O(N * Q). Therefore, we need to find a method to calculate the range sum quickly.

Preprocessing Approach

One efficient method is to store the range sums in a cumulative array through preprocessing. This allows us to calculate the range sum for each query in O(1).

  1. First, create a cumulative sum array sum. Initialize it with sum[0] = 0, and set sum[i] = sum[i - 1] + A[i - 1].
  2. For each query, to find the sum in the range [L, R], use the formula sum[R] - sum[L - 1].

Java Code Implementation

    import java.util.Scanner;

    public class RangeSum {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            // Input the size of the array and the number of queries
            int N = sc.nextInt();
            int Q = sc.nextInt();
            
            // Input the array
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = sc.nextInt();
            }
            
            // Create cumulative sum array
            long[] sum = new long[N + 1];
            for (int i = 1; i <= N; i++) {
                sum[i] = sum[i - 1] + A[i - 1];
            }
            
            // Process each query
            for (int i = 0; i < Q; i++) {
                int L = sc.nextInt();
                int R = sc.nextInt();
                long rangeSum = sum[R] - sum[L - 1];
                System.out.println(rangeSum);
            }
            
            sc.close();
        }
    }

Code Explanation

The code above operates in the following manner:

  1. First, it reads the size of the array N and the number of queries Q from the user.
  2. Then, it initializes the elements of the array A.
  3. A sum array is created to store the cumulative sums of each element, initializing index 0 to 0 to facilitate easy access to sum[i].
  4. For each query, it calculates the range sum using the provided L and R and outputs the result.

Testing and Validation

After writing the code, it is essential to verify that each query returns the correct result through various inputs. In addition to the example input, we should experiment with additional cases and review the results. Here are a few examples:

  • Input: 1 1 → Output: 1
  • Input: 2 5 → Output: 14
  • Input: 3 3 → Output: 3

Conclusion

In this post, we explored the process of solving the range sum problem. It is important to learn how to efficiently calculate range sums through preprocessing, and practicing with arrays and loops in Java will help develop good coding skills. I hope to tackle more algorithm problems in the future to enhance your technical abilities.

Thank you!