{"id":33313,"date":"2024-11-01T09:15:26","date_gmt":"2024-11-01T09:15:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33313"},"modified":"2024-11-01T11:39:14","modified_gmt":"2024-11-01T11:39:14","slug":"java-coding-test-course-range-sum","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33313\/","title":{"rendered":"Java Coding Test Course, Range Sum"},"content":{"rendered":"

<\/p>\n

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.<\/p>\n

Problem Description<\/h2>\n

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

Input<\/h3>\n
\n    The first line contains the size of the array N<\/code> and the number of queries Q<\/code>.\n    The second line contains N<\/code> integers A[1], A[2], ..., A[N]<\/code>.\n    Following that, Q<\/code> lines are given with L<\/code> and R<\/code> separated by space.\n    <\/pre>\n
Output<\/h3>\n
\n    Print the range sum for each query, one per line.\n    <\/pre>\n
Example Input<\/h2>\n
\n    5 3\n    1 2 3 4 5\n    1 3\n    2 4\n    1 5\n    <\/pre>\n
Example Output<\/h2>\n
\n    6\n    9\n    15\n    <\/pre>\n
Problem Solving Strategy<\/h2>\n
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)<\/code>. Therefore, we need to find a method to calculate the range sum quickly.<\/p>\n
Preprocessing Approach<\/h3>\n
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)<\/code>.<\/p>\n
    \n
  1. First, create a cumulative sum array sum<\/code>. Initialize it with sum[0] = 0<\/code>, and set sum[i] = sum[i - 1] + A[i - 1]<\/code>.<\/li>\n
  2. For each query, to find the sum in the range [L, R]<\/code>, use the formula sum[R] - sum[L - 1]<\/code>.<\/li>\n<\/ol>\n
    Java Code Implementation<\/h2>\n
    \n    import java.util.Scanner;\n\n    public class RangeSum {\n        public static void main(String[] args) {\n            Scanner sc = new Scanner(System.in);\n            \n            \/\/ Input the size of the array and the number of queries\n            int N = sc.nextInt();\n            int Q = sc.nextInt();\n            \n            \/\/ Input the array\n            int[] A = new int[N];\n            for (int i = 0; i < N; i++) {\n                A[i] = sc.nextInt();\n            }\n            \n            \/\/ Create cumulative sum array\n            long[] sum = new long[N + 1];\n            for (int i = 1; i <= N; i++) {\n                sum[i] = sum[i - 1] + A[i - 1];\n            }\n            \n            \/\/ Process each query\n            for (int i = 0; i < Q; i++) {\n                int L = sc.nextInt();\n                int R = sc.nextInt();\n                long rangeSum = sum[R] - sum[L - 1];\n                System.out.println(rangeSum);\n            }\n            \n            sc.close();\n        }\n    }\n    <\/pre>\n
    Code Explanation<\/h2>\n
    The code above operates in the following manner:<\/p>\n
      \n
    1. First, it reads the size of the array N<\/code> and the number of queries Q<\/code> from the user.<\/li>\n
    2. Then, it initializes the elements of the array A<\/code>.<\/li>\n
    3. A sum<\/code> array is created to store the cumulative sums of each element, initializing index 0 to 0 to facilitate easy access to sum[i]<\/code>.<\/li>\n
    4. For each query, it calculates the range sum using the provided L<\/code> and R<\/code> and outputs the result.<\/li>\n<\/ol>\n
      Testing and Validation<\/h2>\n
      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:<\/p>\n