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.<\/p>\n
Given an integer array Print the result of each query on a new line.<\/p>\n To find the sum of a specific interval in a 1-indexed array, we can use the following method:<\/p>\n Now, let’s implement the algorithm in Java. Below is the actual code:<\/p>\n The above code is structured as follows:<\/p>\n The time complexity of this algorithm is as follows:<\/p>\nA<\/code> and m<\/code> queries, each query is represented by two integers X<\/code> and Y<\/code>, and the task is to output the value of A[X] + A[X+1] + ... + A[Y]<\/code>. Note that the queries are 1-indexed.<\/p>\nInput Format<\/h2>\n
\n
N<\/code> (the number of elements in the array) and M<\/code> (the number of queries).<\/li>\nA<\/code> consisting of N<\/code> integers.<\/li>\nM<\/code> lines contains two integers X<\/code> and Y<\/code> representing each query.<\/li>\n<\/ul>\nOutput Format<\/h2>\n
Example<\/h2>\n
\nInput Example:\n5 3\n1 2 3 4 5\n1 3\n2 4\n1 5\n\nOutput Example:\n6\n9\n15\n<\/pre>\n
Approach to the Problem<\/h2>\n
\n
sum[Y] - sum[X-1]<\/code>. Here, sum[i]<\/code> is the sum from 1 to i<\/code> in the input array.<\/li>\n<\/ol>\nAlgorithm Implementation<\/h2>\n
import java.util.Scanner;\n\npublic class IntervalSum {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n \/\/ Get the size of the array N and number of queries M\n int N = scanner.nextInt();\n int M = scanner.nextInt();\n\n \/\/ Declare array A and input values\n long[] A = new long[N + 1];\n for (int i = 1; i <= N; i++) {\n A[i] = scanner.nextLong();\n }\n\n \/\/ Declare sum array\n long[] sum = new long[N + 1];\n\n \/\/ Create sum array\n for (int i = 1; i <= N; i++) {\n sum[i] = sum[i - 1] + A[i];\n }\n\n \/\/ Process queries\n for (int j = 0; j < M; j++) {\n int X = scanner.nextInt();\n int Y = scanner.nextInt();\n \/\/ Calculate and output the interval sum\n System.out.println(sum[Y] - sum[X - 1]);\n }\n\n \/\/ Close the scanner\n scanner.close();\n }\n}<\/code><\/pre>\nCode Explanation<\/h2>\n
\n
Scanner<\/code> to receive input. It reads the size of the array (N<\/code>) and the number of queries (M<\/code>).<\/li>\nA<\/code> and assigns values in a 1-indexed manner.<\/li>\nsum<\/code>. This array stores the sum from 1 to i<\/code> of the array A<\/code>.<\/li>\nX<\/code> and Y<\/code>, calculates the interval sum, and prints the result.<\/li>\n<\/ol>\nTime Complexity Analysis<\/h2>\n