We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum Of Special Evenly-Spaced Elements In Array

Number: 1809

Difficulty: Hard

Paid? Yes

Companies: MakeMyTrip, Sprinklr

Problem Description

You are given a 0-indexed integer array nums and an array queries where each query is of the form [x, y]. For each query you need to sum all elements nums[j] for indices j starting from x (inclusive) such that the difference (j - x) is divisible by y. The final answer for each query is the computed sum modulo 10^9 + 7.

Key Insights

  • Notice that for any query [x, y], the valid indices are x, x+y, x+2y, … until the index reaches the end of the nums array.
  • For queries with a small step (small y), many indices will be summed. We can preprocess these queries using dynamic programming (by precomputing answers for every starting index x).
  • For queries with large y, there are only a few terms (since the jump is large). In these cases, iterating directly over the indices works efficiently.
  • Combining both approaches by choosing a threshold (typically near √n) to decide whether to precompute or iterate directly provides an optimized solution.

Space and Time Complexity

Time Complexity: O(n * t + Q * (n / y)) where t is the threshold (≈√n) and Q is the number of queries. This results in roughly O(n√n + total iterations for large y queries). Space Complexity: O(n * t) for storing the precomputed answers for small-step queries.

Solution

We choose a threshold value (for example, t = floor(sqrt(n))) to decide our approach. For each y <= t, we precompute an array dp[y] where for every starting index x the value dp[y][x] is the sum of nums[x] + nums[x+y] + nums[x+2y] + ... (taking modulo 10^9 + 7). This precomputation is done in reverse order (from n-1 down to 0) so that dp[y][x] = nums[x] + (dp[y][x+y] if x+y < n, else 0).

For queries with y > t, the number of elements in the sum is small since the indices skip ahead by a large number. These queries are handled directly by iterating from x while staying in bounds and summing the required elements.

Key details include: • Using modulo arithmetic (mod = 10^9 + 7) at every sum update. • Choosing a threshold that balances the extra cost of precomputation with the direct iteration cost. • The precomputed dp arrays allow O(1) retrieval for queries with y <= t.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

def sum_special_elements(nums, queries):
    n = len(nums)
    # threshold chosen as the integer square root of n for balancing precomputation vs direct iteration
    threshold = int(n**0.5)
    # dp will store precomputed sums for small y values
    dp = {}
    # precompute for each small step value from 1 to threshold
    for y in range(1, threshold + 1):
        dp[y] = [0] * n
        # iterate from the end of the array to start to compute dp[y][x]
        for x in range(n - 1, -1, -1):
            add = dp[y][x + y] if x + y < n else 0
            dp[y][x] = (nums[x] + add) % MOD

    results = []
    for x, y in queries:
        if y <= threshold:
            # use precomputed results if y is small
            results.append(dp[y][x])
        else:
            # for larger y, compute by iterating over the valid indices
            total = 0
            # iterate from index x while index < n
            pos = x
            while pos < n:
                total = (total + nums[pos]) % MOD
                pos += y
            results.append(total)
    return results

# Example usage:
if __name__ == "__main__":
    nums = [0, 1, 2, 3, 4, 5, 6, 7]
    queries = [[0, 3], [5, 1], [4, 2]]
    print(sum_special_elements(nums, queries))  # Expected output: [9, 18, 10]
← Back to All Questions