Calculate cumulative sum of GCDs for array range queries
Filed under Deutsche Bank
Free read 1 of 3Confirm if indices are 0-based or 1-based and if the array is static.
The question
Given an array A and a list of queries (l, r), calculate the sum of GCD(A[l], A[r]) for all queries.
Constraints
- 1 <= len(A) <= 10^5
- 1 <= num_queries <= 10^5
- 1 <= A[i] <= 10^6
Examples
- Input
- A = [12, 6, 18], queries = [(0, 1), (1, 2)]
- Output
- 12
- Why
- GCD(12, 6) = 6; GCD(6, 18) = 6; Sum = 12.
Approach
Confirm if indices are 0-based or 1-based and if the array is static.
Iterate through each query and compute GCD using the Euclidean algorithm. Time complexity O(Q * log(min(A[i]))).
Since queries are specific indices (l, r), precompute GCD values if the array is static or use a Sparse Table if queries were range-based.
Solution
O(Q * log(max(A))) time, O(1) space
import math
def solve(A, queries):
total = 0
for l, r in queries:
total += math.gcd(A[l], A[r])
return total
Tips
- What they are testing: Tests efficiency with large arrays and many queries.
- Common mistake: Using a naive O(N) GCD calculation per query instead of precomputing or using efficient math properties.
Related Deutsche Bank questions
Collected from public candidate posts and coding forums. Updated Nov 2026.