Java Kotlin Coding Test Course, Finding the Sum of Intervals 1

Hello! In this post, we will take a closer look at how to solve the problem of calculating the sum of intervals using Kotlin.
The interval sum problem is a common type encountered in programming contests and coding tests, and knowing how to solve it efficiently can help you quickly solve various problems.

Problem Description

The task is to calculate the sum of a specific interval when given an array. The aim is to solve the problem of
calculating the sum for each interval given the array and several queries. For example, let’s assume the array A is as follows:

        A = [10, 20, 30, 40, 50]
    

In this case, when we receive a query to find the sum in the interval (i, j) specified by the user,
we need to return the corresponding sum.

Input Format

The first line contains the size of the array N and the number of queries M.
Then, N integers are provided to form the array A.
The next M lines each contain two integers i and j,
indicating a query to calculate the sum from A[i] to A[j].

Output Format

Print the sum for each query.

Example Input

    5 3
    10 20 30 40 50
    1 3
    2 4
    1 5
    

Example Output

    60
    90
    150
    

Approach to Solve the Problem

There are two ways to solve this problem.
The first method is to simply iterate and calculate the sum for each query,
and the second is to use the prefix sum array.
The second method is much more efficient, so I will focus on explaining that.

Prefix Sum Array

By using a prefix sum array, we can calculate the interval sum in O(1) time complexity for each query.
Since calculating the prefix sum array takes O(N) time,
the total time complexity is O(N + M).
This becomes more efficient as the number of queries increases.

Definition of Prefix Sum Array

A prefix sum array is an array that stores the cumulative sums of a given array.
Specifically, we define an array S that stores the sum up to the i-th index of array A.
It is represented as S[i] = A[0] + A[1] + ... + A[i-1].

How to Calculate Interval Sums

The sum from A[i] to A[j] can be calculated as follows:
sum = S[j+1] - S[i]

Here, S[j+1] is the sum from A[0] to A[j],
and S[i] is the sum from A[0] to A[i-1].
Therefore, by subtracting S[i] from S[j+1], we obtain the sum from A[i] to A[j].

Code Implementation

Now, let’s write the code to solve this problem using Kotlin.

Kotlin Code

    fun main() {
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        val a = readLine()!!.split(" ").map { it.toInt() }
        
        val s = IntArray(n + 1)
        
        for (i in 1..n) {
            s[i] = s[i - 1] + a[i - 1]
        }
        
        repeat(m) {
            val (i, j) = readLine()!!.split(" ").map { it.toInt() }
            println(s[j] - s[i - 1])
        }
    }
    

Code Explanation

1. The first line reads N and M.
2. The second line reads the array A.
3. The prefix sum array S is initialized with a size of N + 1.
4. A loop calculates the values for the prefix sum array S.
5. For each query, we calculate and print the sum for the respective interval.

Conclusion

The interval sum problem is a useful technique that can be applied to various problems.
Using a prefix sum array in Kotlin allows us to solve the problem much faster.
I hope this tutorial helps you enhance your understanding of the interval sum problem and
allows you to effectively utilize it in coding tests.

In the next post, we will explore other types of problems extending the concept of interval sums.
Keep continuing your learning!