{"id":34958,"date":"2024-11-01T09:34:01","date_gmt":"2024-11-01T09:34:01","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34958"},"modified":"2024-11-01T11:45:35","modified_gmt":"2024-11-01T11:45:35","slug":"android-coding-test-course-finding-interval-sum-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34958\/","title":{"rendered":"Android Coding Test Course, Finding Interval Sum 2"},"content":{"rendered":"

<\/p>\n

Among the various algorithms dealt with in coding tests, the ‘interval sum’ problem is frequently encountered.
\nIn this post, we will solve a problem titled Calculating Interval Sums 2<\/strong>.
\nWe will particularly utilize the Kotlin programming language for this.<\/p>\n

Problem Description<\/h2>\n

This problem presents a method to efficiently calculate the sum of a specific interval given multiple integers.
\nHere is the definition of the problem:<\/p>\n

\nGiven integers N and M, \nN integers will be provided, \nand M queries will be given. \nEach query consists of two integers i and j, \nand the sum of integers between i and j needs to be calculated.\n\nInput Format:\n- The first line will contain N (1 \u2264 N \u2264 100,000) and M (1 \u2264 M \u2264 100,000).\n- The second line contains N integers. Each integer does not exceed 1,000,000.\n- Following M lines, i and j will be given. (1 \u2264 i \u2264 j \u2264 N)\n\nOutput Format:\n- For each query, output the sum from the i-th to the j-th number.\n<\/pre>\n
Problem Solving Process<\/h2>\n
To solve this problem, an efficient algorithm is needed. Simply looping through each query to calculate the sum would result in a time complexity of O(N*M), which may lead to a timeout failure if the input is large.<\/p>\n
1. Using Cumulative Sum Array<\/h3>\n
Instead of calculating all sums each time from a checking perspective, there is the option of using a cumulative sum array. By utilizing the cumulative sum array, the sum of a specific interval can be determined with O(1) time complexity.<\/p>\n
Defining the cumulative sum array prefixSum<\/code>, prefixSum[k]<\/code> represents the sum from the start of the array to the k-th number.
\nTherefore, it holds the following relationship:<\/p>\n
\nprefixSum[k] = prefixSum[k-1] + array[k-1] (1 \u2264 k \u2264 N)\n<\/pre>\n
In this case, the sum of a specific interval can be calculated as follows:<\/p>\n
\nsum(i, j) = prefixSum[j] - prefixSum[i-1]\n<\/pre>\n
2. Implementing the Algorithm<\/h3>\n
Now, let’s implement the code based on this idea.
\nThe following code is an example of solving the problem using Kotlin:<\/p>\n
\nfun main() {\n    val (n, m) = readLine()!!.split(\" \").map { it.toInt() }\n    val numbers = readLine()!!.split(\" \").map { it.toInt() }.toIntArray()\n    val prefixSum = LongArray(n + 1)\n\n    for (i in 1..n) {\n        prefixSum[i] = prefixSum[i - 1] + numbers[i - 1].toLong()\n    }\n\n    for (j in 0 until m) {\n        val (i, j) = readLine()!!.split(\" \").map { it.toInt() }\n        println(prefixSum[j] - prefixSum[i - 1])\n    }\n}\n<\/code><\/pre>\n
3. Code Explanation<\/h3>\n
Let me explain how the above code calculates the interval sum:<\/p>\n