โ† Deutsche Bank questions

Calculate cumulative sum of GCDs for array range queries

Filed under Deutsche Bank

Free read 1 of 3

Confirm 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

  1. Confirm if indices are 0-based or 1-based and if the array is static.

Solution

O(Q * log(max(A))) time, O(1) space

Python
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.