Android Coding Test Course, Finding Interval Sum 2

Among the various algorithms dealt with in coding tests, the ‘interval sum’ problem is frequently encountered.
In this post, we will solve a problem titled Calculating Interval Sums 2.
We will particularly utilize the Kotlin programming language for this.

Problem Description

This problem presents a method to efficiently calculate the sum of a specific interval given multiple integers.
Here is the definition of the problem:

Given integers N and M, 
N integers will be provided, 
and M queries will be given. 
Each query consists of two integers i and j, 
and the sum of integers between i and j needs to be calculated.

Input Format:
- The first line will contain N (1 ≤ N ≤ 100,000) and M (1 ≤ M ≤ 100,000).
- The second line contains N integers. Each integer does not exceed 1,000,000.
- Following M lines, i and j will be given. (1 ≤ i ≤ j ≤ N)

Output Format:
- For each query, output the sum from the i-th to the j-th number.

Problem Solving Process

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.

1. Using Cumulative Sum Array

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.

Defining the cumulative sum array prefixSum, prefixSum[k] represents the sum from the start of the array to the k-th number.
Therefore, it holds the following relationship:

prefixSum[k] = prefixSum[k-1] + array[k-1] (1 ≤ k ≤ N)

In this case, the sum of a specific interval can be calculated as follows:

sum(i, j) = prefixSum[j] - prefixSum[i-1]

2. Implementing the Algorithm

Now, let’s implement the code based on this idea.
The following code is an example of solving the problem using Kotlin:


fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val numbers = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val prefixSum = LongArray(n + 1)

    for (i in 1..n) {
        prefixSum[i] = prefixSum[i - 1] + numbers[i - 1].toLong()
    }

    for (j in 0 until m) {
        val (i, j) = readLine()!!.split(" ").map { it.toInt() }
        println(prefixSum[j] - prefixSum[i - 1])
    }
}

3. Code Explanation

Let me explain how the above code calculates the interval sum:

  • val (n, m) = readLine()!!.split(" ").map { it.toInt() }:
    Reads N and M from the first line.
  • val numbers = readLine()!!.split(" ").map { it.toInt() }.toIntArray():
    Receives N integers from the second line and converts them into an array.
  • val prefixSum = LongArray(n + 1):
    Creates an array to store cumulative sums. (The 0th index is initialized to 0)
  • for (i in 1..n):
    Uses a loop to calculate the cumulative sums. Saves the sum to prefixSum[i] up to the i-th number.
  • for (j in 0 until m):
    Receives input for each query and calculates the interval sum.
  • println(prefixSum[j] - prefixSum[i - 1]):
    Outputs the sum from the i-th index to the j-th index.

Complexity Analysis

The time complexity of the above code is as follows:

  • Time taken to create the cumulative sum array: O(N)
  • Time taken to calculate the interval sum for each of the M queries: O(M)

Therefore, the overall time complexity is O(N + M). This is a good method for effectively handling the interval sums of the given problem.

Conclusion

In this lecture, we efficiently solved the problem of calculating interval sums 2 using cumulative sums.
This approach can be effectively applied to many algorithm problems, so try to apply it to various challenges.

We dealt with the problem of quickly and efficiently calculating the sum of a specific interval from an array consisting of multiple integers.
We have learned that various algorithm problems can be solved using data structures such as arrays and lists in Kotlin.

Additional Practice Problems

Please practice the following additional problems:

  • Finding the minimum and maximum value of intervals in various query forms
  • Finding unusual interval sums: Summing only intervals that meet specific conditions
  • Finding interval sums in multidimensional arrays

I hope this post helps you prepare for your coding tests.
Thank you!