C++ Coding Test Course, Finding Interval Sum 1

Hello! In this session, we will enhance our algorithm problem-solving skills through the ‘Range Sum’ problem, which frequently appears in C++ coding tests. The Range Sum problem aims to find the sum of elements in a specific range of a given array, and we will explore various methods and optimization techniques to solve this problem.

Problem Description

We are given an integer array A and an integer M. For each element in A, we need to find the sum of the range starting from A[i] in the form of A[i] + A[i+1] + ... + A[j]. Below are the specific requirements of the problem.

Problem

Given an integer array A and an integer M, implement a function to find the sum of M consecutive elements starting from A[i].

Input

• The first line contains the length of the array N. (1 ≤ N ≤ 100,000)
• The second line contains N integers forming the array A. (−1,000,000,000 ≤ A[i] ≤ 1,000,000,000)
• The third line contains the integer M. (1 ≤ M ≤ N)

Output

Output the range sum. If the sum of M elements starting from A[i] is possible, print that sum; otherwise, print -1.

Solution Process

There are various approaches to solve this problem, but the most common and efficient method is using the Sliding Window technique. By using the sliding window technique, we can solve the problem with a time complexity of O(N).

Explanation of the Sliding Window Approach

In the sliding window technique, we set the start and end of the range like a window and calculate the value of that range by moving the window. After setting the initial range, we update the sum by adding the next element and subtracting the starting element. This reduces unnecessary calculations and increases efficiency.

Code Implementation

Now let’s implement our approach in C++.

#include <iostream>
#include <vector>
using namespace std;

// Function: Calculate range sum
long long rangeSum(const vector<int> &A, int M) {
    long long sum = 0; // Initial sum variable
    int N = A.size(); // Array size

    // Calculate the sum of the first range
    for (int i = 0; i < M; i++) {
        sum += A[i];
    }
    
    // Print the sum of the first range
    cout << "Range Sum: " << sum << endl;

    // Update the range sum using the sliding window
    for (int i = M; i < N; i++) {
        sum += A[i] - A[i - M]; // Subtract the old element and add the new element
        cout << "Range Sum: " << sum << endl; // Print the updated range sum
    }
    
    return sum; // Final return value
}

int main() {
    int N, M;
    cout << "Length of the array N: ";
    cin >> N; // Input array size
    vector<int> A(N);

    cout << "Integer array A: ";
    for (int i = 0; i < N; i++) {
        cin >> A[i]; // Input array elements
    }

    cout << "Length of the range M: ";
    cin >> M; // Input length of range sum

    long long totalSum = rangeSum(A, M); // Call the range sum function
    if (N < M) {
        cout << "-1" << endl; // Print -1 if range sum is not possible
    } else {
        cout << "Total of range sums: " << totalSum << endl; // Print the total sum
    }

    return 0;
}
    

Code Explanation

The above code shows the process of calculating the range sum as follows:

1. First, we input the array A of size N and the range length M.
2. To calculate the initial range sum, we sum the first M elements.
3. By applying the sliding window technique, we get the next range sum by subtracting the existing element and adding the new element.
4. Output all range sums.

Conclusion

In this session, we solved the problem of calculating the range sum using C++. The sliding window technique is a very simple yet efficient method, making it useful for solving various problems. Familiarizing yourself with techniques like this will greatly help you prepare for coding tests.

In the next lecture, we will cover more diverse problems and help deepen your understanding of algorithms. Until then, practice and best of luck!