sum-of-special-evenly-spaced-elements-in-array

< Previous 　　　　　　　　　　　　　　　　 Next >

1714. Sum Of Special Evenly-Spaced Elements In Array (Hard)

Related Topics

[Array] [Dynamic Programming]

Hints

Hint 1

Think if y cannot be small. You can solve a query in O(n/y), so if y is large enough, it won't be a problem.

Hint 2

If y is small, like less than B, you can preprocess the answers for all such ys in O(n * B), then answer each such query in O(1).

Hint 3

As you might have already guessed, the optimal value for B is ~sqrt(n).