Hello! Today, we will address one of the frequently asked problems in coding tests using C#, which is the “Calculate Interval Sum” problem. Through this problem, we aim to enhance our understanding of arrays and interval sums, and learn algorithms to solve this efficiently.
Problem Description
The interval sum problem can be defined as follows:
Given an integer array arr and several queries (starting index and ending index), write a program to calculate the sum of the respective interval for each query.
The input consists of the size of the array n, the elements of the array, the number of queries q, and the starting index l and ending index r for each query.
Input Example
5
1 2 3 4 5
3
1 3
2 4
1 5
The above input is as follows:
- Array size:
5 - Array elements:
[1, 2, 3, 4, 5] - Number of queries:
3 - Queries: (1, 3), (2, 4), (1, 5)
Output Example
6
9
15
The output is the interval sum for each query:
- Interval sum for (1, 3):
1 + 2 + 3 = 6 - Interval sum for (2, 4):
2 + 3 + 4 = 9 - Interval sum for (1, 5):
1 + 2 + 3 + 4 + 5 = 15
Solving the Problem
Now, let’s go through the steps to solve this problem. We will start with a simple approach and then progress to a more efficient method.
1. Simple Approach
The most intuitive method is to directly calculate the sum according to the starting and ending indices of each query. However, this method can be inefficient. For example, in the worst case, if the size of the array is n and the number of queries is q, the time complexity can reach O(n * q).
C#
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int q = int.Parse(Console.ReadLine());
for (int i = 0; i < q; i++)
{
var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int l = query[0] - 1; // 0-based index
int r = query[1] - 1; // 0-based index
int sum = 0;
for (int j = l; j <= r; j++)
{
sum += arr[j];
}
Console.WriteLine(sum);
}
}
}
This code calculates the sum for each query based on the input array elements provided by the user. However, this method is inefficient for large datasets.
2. Efficient Approach: Cumulative Sum Array
An efficient way is to use a cumulative sum array. The cumulative sum pre-calculates the sum up to each index in the array, reducing the processing time for queries.
That is,
C#
sum[i] = arr[0] + arr[1] + ... + arr[i]
To calculate the interval sum:
C#
interval_sum = sum[r] - sum[l-1]
This reduces the query processing time to O(1). The overall time complexity becomes O(n + q).
C#
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int q = int.Parse(Console.ReadLine());
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + arr[i - 1];
}
for (int i = 0; i < q; i++)
{
var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int l = query[0] - 1; // 0-based index
int r = query[1] - 1; // 0-based index
long result = sum[r + 1] - sum[l];
Console.WriteLine(result);
}
}
}
This code first computes the cumulative sum array and then efficiently calculates the interval sum for each query using the starting and ending indices.
Conclusion
The interval sum problem frequently appears in coding tests, and we can see that using a cumulative sum array is an efficient solution. This method is particularly advantageous when the size of the array and the number of queries are large. Using appropriate data structures to enhance the efficiency of an algorithm and reduce query processing time is a critical factor in solving algorithm problems.
Based on what we've learned today, try practicing various interval sum problem-solving exercises. Thank you!