Calculating Total Points Scored by a Team in a Series of Matches — Problem Statement & Solution Guide
Problem Description
You are given an integer array scores of length n and two zero‑based indices l and r with 0 ≤ l ≤ r < n. Compute the sum of all elements from scores[l] to scores[r] inclusive. The input consists of three lines: the first line contains n, the second line contains n space‑separated integers representing scores, and the third line contains the two indices l and r. Output a single integer – the required sum.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Calculating Total Points Scored by a Team in a Series of Matches"
WHY DOES IT MATTER?
Range‑sum queries appear in analytics, finance, and gaming where you frequently need totals over sliding windows; mastering prefix sums gives you a constant‑time answer after linear preprocessing.
OPTIMIZATION CHALLENGE
The insight is to store partial aggregates once (the prefix array) instead of recomputing them for every query, turning repeated O(k) scans into O(1) look‑ups.
REAL-WORLD CONNECTION
Think of a bank ledger where each entry records daily profit; the cumulative balance at day i is the prefix sum, and the profit between days l and r is just the difference of two balances—mirroring how distributed systems compute aggregates from checkpoints.
When coding, first read the whole array, build the prefix array in a single pass, and then answer the query with a one‑liner; this avoids off‑by‑one errors and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The task of summing a sub‑array is a classic example of range query problems. A naïve solution scans the segment from index l to r for each query, leading to O(r‑l+1) time per query, which becomes prohibitive when the array is large or when many queries are asked. The optimal paradigm uses a prefix‑sum (cumulative‑sum) array: prefix[i] stores the sum of the first i elements, allowing any range sum to be answered in O(1) by computing prefix[r+1]‑prefix[l]. Building the prefix array itself costs O(n) time and O(n) extra space, but it amortises the cost across all queries, turning a potentially quadratic workload into linear preprocessing followed by constant‑time answers.
Interview Questions on This Problem
Q1How would you modify your solution if you had to answer Q = 10⁵ range‑sum queries on the same array?
Pre‑compute a prefix‑sum array in O(n) time; each query then returns prefix[r+1]‑prefix[l] in O(1), giving overall O(n+Q) time and O(n) space.
Q2What data structure can answer dynamic range‑sum queries where the array elements may change?
A Binary Indexed Tree (Fenwick) or a Segment Tree supports point updates and range‑sum queries in O(log n) time each.
Q3Why might using a 32‑bit integer for the cumulative sum cause bugs, and how do you prevent it?
If the sum exceeds 2³¹‑1 it overflows; using a 64‑bit type (long long in C++, long in Java, int64 in Go) safely accommodates the maximum possible sum.
Examples
Input
5 3 7 2 9 4 1 3
Output
18
Explanation: The sub‑array defined by indices 1 to 3 is [7,2,9]. Adding them yields 7+2+9=18.
Input
6 -5 10 0 -2 8 3 0 5
Output
14
Explanation: All elements are included: -5+10+0-2+8+3=14.
Input
4 1000000000 1000000000 1000000000 1000000000 2 3
Output
2000000000
Explanation: Indices 2 and 3 cover the last two numbers, each 1,000,000,000. Their sum is 2,000,000,000.
Constraints
- 1 <= n <= 100000
- -10^9 <= scores[i] <= 10^9
- 0 <= l <= r < n
Optimal Approach & Strategy
Build a prefix‑sum array in one pass (O(n)), then compute the answer as prefix[r+1]‑prefix[l] in O(1).
Brute Force Approach
Loop from l to r, adding each element to an accumulator; this directly follows the problem statement but costs O(r‑l+1) time.
Verified Code Solutions
function rangeSum(scores, l, r) {
let sum = 0;
for(let i=l;i<=r;i++) sum += scores[i];
return sum;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const scores=data.slice(idx, idx+n); idx+=n;
const l=data[idx++];
const r=data[idx++];
console.log(rangeSum(scores,l,r));
}
main();#include <bits/stdc++.h>
using namespace std;
long long rangeSum(const vector<int>& scores, int l, int r) {
long long sum = 0;
for(int i=l;i<=r;++i) sum += scores[i];
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> scores(n);
for(int &x:scores) cin>>x;
int l,r; cin>>l>>r;
cout<<rangeSum(scores,l,r);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
static long rangeSum(int[] scores, int l, int r) {
long sum = 0L;
for(int i=l;i<=r;i++) sum += scores[i];
return sum;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null) return;
int n = Integer.parseInt(line.trim());
int[] scores = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) scores[i]=Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
System.out.println(rangeSum(scores,l,r));
}
}def range_sum(scores, l, r):
return sum(scores[l:r+1])
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it))
scores = [int(next(it)) for _ in range(n)]
l = int(next(it))
r = int(next(it))
print(range_sum(scores, l, r))
if __name__ == "__main__":
main()
function rangeSum(scores, l, r) {
let sum = 0;
for(let i=l;i<=r;i++) sum += scores[i];
return sum;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const scores=data.slice(idx, idx+n); idx+=n;
const l=data[idx++];
const r=data[idx++];
console.log(rangeSum(scores,l,r));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.