Hello! Today, we will discuss the coding test problem “Finding the Sum of Intervals 3” using Kotlin. This problem requires efficiently calculating the sum of a specific interval of a given array. Such efficient algorithms are particularly important when needing to calculate interval sums repeatedly.
Problem Description
You are given an array A consisting of N integers and Q queries. Each query contains two integers L and R, which require calculating the sum from the L-th index to the R-th index of array A. Note that the array starts from index 1. You are to output the result for all Q queries.
Input Format
First line: N (1 ≤ N ≤ 100,000)
Second line: N integers (each integer is -10,000,000 ≤ A[i] ≤ 10,000,000)
Third line: Q (1 ≤ Q ≤ 100,000)
The following Q lines contain each query in the form of L R.
Output Format
Output the interval sum for each of the Q lines.
Approach
The basic method is to directly traverse the array to calculate the sum for the given L and R. However, this has a time complexity of O(Q * N), which could involve up to 1 billion operations in the worst case when both Q and N reach their maximum of 100,000. Therefore, this approach is inefficient. This problem requires a method to handle queries with a time complexity of O(1) through preprocessing.
One of the efficient methods to solve the interval sum problem is to use a cumulative sum array. By using the cumulative sum array, the sum for a specific interval L ~ R can be easily calculated.
Cumulative Sum Array
Define the cumulative sum array P. P[i] stores the sum from the first element of array A to the i-th element.
P[i] = A[1] + A[2] + ... + A[i]
The sum for the interval L ~ R can then be calculated as follows:
sum(L, R) = P[R] - P[L - 1]
This method allows us to compute the cumulative sum array in O(N), and subsequently obtain results for each query in O(1). The overall time complexity becomes O(N + Q).
Code Implementation
Kotlin Code
fun main() {
val reader = System.`in`.bufferedReader()
val n = reader.readLine().toInt()
val a = reader.readLine().split(" ").map { it.toInt() }
val q = reader.readLine().toInt()
// Initialize cumulative sum array
val p = LongArray(n + 1)
// Calculate cumulative sum
for (i in 1..n) {
p[i] = p[i - 1] + a[i - 1]
}
val result = StringBuilder()
for (i in 0 until q) {
val (l, r) = reader.readLine().split(" ").map { it.toInt() }
// Calculate interval sum
result.append(p[r] - p[l - 1]).append("\n")
}
// Print results
println(result.toString())
}
Code Explanation
The above code is a solution to the “Finding the Sum of Intervals 3” problem written in Kotlin. Let’s explain each part.
1. Input Handling
First, it receives the values for N, A, and Q. N signifies the size of the array, A is the integer array, and Q represents the number of given queries.
2. Cumulative Sum Array Creation
A cumulative sum array P is created. P[0] is initialized to 0 and the cumulative sums from P[1] to P[n] are calculated. This will store the results of adding each element of the array A.
3. Query Processing
For each query, the L and R values are received, allowing the interval sum to be computed within O(1) time using the cumulative sum array. This result is added to a StringBuilder and printed at the end.
Conclusion
Through the “Finding the Sum of Intervals 3” problem, we learned the importance of using cumulative sum arrays. This technique allows the efficient handling of queries even with large datasets. When solving algorithm problems, it is essential to find the optimal method by considering time complexity. I hope this helps you prepare for your coding tests.
Learn More
In the next lecture, we will cover a variety of algorithm problems. Keep preparing for coding tests and practice a lot. Thank you!