3792. Sum of Increasing Product Blocks 🔒

MediumMathSimulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

A sequence is built using blocks, where each block is formed by multiplying together a set of consecutive integers. The rules for constructing the blocks are as follows:

The 1st block contains 1. This is the product of the first 1 consecutive integer, which is just 1.
The 2nd block contains 2 * 3. This is the product of the next 2 consecutive integers, which are 2 and 3.
The 3rd block would contain 4 * 5 * 6. This is the product of the next 3 consecutive integers.
In general, the ith block is the product of the next i consecutive integers, picking up right where the previous block left off.

To understand how the integers are distributed:

Block 1 uses the integer 1 (1 number).
Block 2 uses the integers 2, 3 (2 numbers).
Block 3 uses the integers 4, 5, 6 (3 numbers).
Block 4 uses the integers 7, 8, 9, 10 (4 numbers).

Each block consumes consecutive integers starting from where the previous block ended, with the ith block consuming exactly i integers.

Let F(n) be the sum of the values of the first n blocks. For example, F(3) would be calculated as:

F(3) = (1) + (2 * 3) + (4 * 5 * 6) = 1 + 6 + 120 = 127

Because the products can grow extremely large, you must return the value of F(n) modulo 10^9 + 7.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Computing blocks of consecutive integer products and summing them modulo MOD is a direct simulation of the described block construction.

Open in Flowchart

Intuition

The key observation is that the problem describes a very clear, step-by-step construction process, and we can follow it directly. There's no hidden trick or clever formula needed — we just need to faithfully simulate what the problem describes.

Let's think about what information we need to build each block:

For the ith block, we need to know which integer to start from. Notice that the starting integer of each block depends on how many integers were consumed by all the previous blocks. Since block 1 uses 1 number, block 2 uses 2 numbers, and so on, the total numbers used before block i is 1 + 2 + ... + (i - 1).
Instead of recomputing this sum every time, we can keep a running pointer (let's call it k) that always points to the first integer of the current block. After finishing a block of size i, we simply advance the pointer by i, so it lands exactly on the start of the next block.

With the starting point known, building each block is straightforward: we multiply together i consecutive integers beginning at k. We accumulate each block's product into a running total to compute F(n).

The only complication is that these products grow very fast — factorial-like growth — and would quickly overflow into enormous numbers. To handle this, we rely on a property of modular arithmetic: taking the modulo at every multiplication step gives the same result as taking it only at the end. So we apply % (10^9 + 7) during each multiplication and each addition. This keeps all intermediate values small and manageable while preserving the correct final answer.

In short, the intuition is: track the starting integer with a moving pointer, multiply the consecutive integers for each block, sum them up, and keep everything under control using modulo at every step.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Simulation

We directly simulate the construction of each block and accumulate the products into the answer. The implementation uses simple variables and two nested loops — no advanced data structures are required.

Let's walk through the implementation step by step:

Initialize the variables.
- ans = 0 holds the running sum F(n).
- mod = 10**9 + 7 is the modulus we apply throughout.
- k = 1 is the pointer to the first integer of the current block. It starts at 1 because the very first block begins with the integer 1.
Loop over each block. We iterate i from 1 to n (inclusive). Here i represents both the block index and the number of integers that block contains.
Compute the product of the current block.
- We set x = 1 as the starting value for the product.
- We loop j over the range [k, k + i), which gives exactly the i consecutive integers belonging to this block.
- For each j, we update x = (x * j) % mod. Applying the modulo at every multiplication keeps x small and prevents overflow into huge numbers.
Add the block's product to the answer.
- We update ans = (ans + x) % mod, again taking the modulo to keep the sum bounded.
Advance the pointer.
- We do k += i so that k now points to the first integer of the next block. This is what links the blocks together — each one picks up exactly where the previous one ended.
Return the result. After processing all n blocks, ans holds F(n) modulo 10^9 + 7, which we return.

Complexity Analysis:

Time complexity: The outer loop runs n times, and for block i the inner loop runs i times. The total number of multiplications is 1 + 2 + ... + n, which is O(n^2).
Space complexity: O(1), since we only use a few scalar variables regardless of the input size.

Example Walkthrough

Let's trace through the solution approach with a small example: n = 4. We want to compute F(4) = (1) + (2 * 3) + (4 * 5 * 6) + (7 * 8 * 9 * 10).

Initial Setup:

ans = 0 (running sum)
mod = 10^9 + 7
k = 1 (pointer to the first integer of the current block)

Now we loop i from 1 to 4.

Iteration i = 1 (block of size 1):

Start product x = 1.
Inner loop j ranges over [1, 1 + 1) = [1, 2), so just j = 1.
- x = (1 * 1) % mod = 1
Add to answer: ans = (0 + 1) % mod = 1
Advance pointer: k = 1 + 1 = 2

Block 1 contributes 1. Pointer now sits at 2.

Iteration i = 2 (block of size 2):

Start product x = 1.
Inner loop j ranges over [2, 2 + 2) = [2, 4), so j = 2, 3.
- x = (1 * 2) % mod = 2
- x = (2 * 3) % mod = 6
Add to answer: ans = (1 + 6) % mod = 7
Advance pointer: k = 2 + 2 = 4

Block 2 contributes 6. Pointer now sits at 4.

Iteration i = 3 (block of size 3):

Start product x = 1.
Inner loop j ranges over [4, 4 + 3) = [4, 7), so j = 4, 5, 6.
- x = (1 * 4) % mod = 4
- x = (4 * 5) % mod = 20
- x = (20 * 6) % mod = 120
Add to answer: ans = (7 + 120) % mod = 127
Advance pointer: k = 4 + 3 = 7

Block 3 contributes 120. Pointer now sits at 7.

Iteration i = 4 (block of size 4):

Start product x = 1.
Inner loop j ranges over [7, 7 + 4) = [7, 11), so j = 7, 8, 9, 10.
- x = (1 * 7) % mod = 7
- x = (7 * 8) % mod = 56
- x = (56 * 9) % mod = 504
- x = (504 * 10) % mod = 5040
Add to answer: ans = (127 + 5040) % mod = 5167
Advance pointer: k = 7 + 4 = 11

Block 4 contributes 5040. Pointer now sits at 11.

Final Result:

After all 4 iterations, ans = 5167. We return 5167.

Let's verify: 1 + 6 + 120 + 5040 = 5167. ✓

Key takeaways from this trace:

The pointer k smoothly carries us from one block to the next (1 → 2 → 4 → 7 → 11), so we never recompute where a block starts.
The values consumed by each block are exactly i consecutive integers, matching the problem's distribution rule.
Because the numbers here are small, no actual reduction happened at the % mod steps — but for large n, that modulo is what keeps the products from exploding.

Solution Implementation

1class Solution:
2    def sumOfBlocks(self, n: int) -> int:
3        MOD = 10**9 + 7
4
5        total = 0          # Running sum of all block products
6        start = 1          # Starting integer of the current block
7
8        # Build n blocks; the i-th block contains i consecutive integers
9        for block_size in range(1, n + 1):
10            product = 1    # Product of integers within the current block
11
12            # Multiply the block_size consecutive integers beginning at `start`
13            for value in range(start, start + block_size):
14                product = (product * value) % MOD
15
16            # Accumulate this block's product into the total
17            total = (total + product) % MOD
18
19            # Move the start pointer past the integers used in this block
20            start += block_size
21
22        return total
23

1class Solution {
2    public int sumOfBlocks(int n) {
3        // Modulus value to prevent integer overflow
4        final int MOD = (int) 1e9 + 7;
5
6        // Accumulator for the final answer
7        long answer = 0;
8
9        // Starting number for the current block
10        int blockStart = 1;
11
12        // Iterate over each block, where block i contains i consecutive numbers
13        for (int block = 1; block <= n; ++block) {
14            // Product of all numbers within the current block
15            long product = 1;
16
17            // Multiply the consecutive numbers in this block:
18            // from blockStart to blockStart + block - 1
19            for (int num = blockStart; num < blockStart + block; ++num) {
20                product = product * num % MOD;
21            }
22
23            // Add the current block's product to the answer
24            answer = (answer + product) % MOD;
25
26            // Advance the starting number for the next block
27            blockStart += block;
28        }
29
30        return (int) answer;
31    }
32}
33

1class Solution {
2public:
3    int sumOfBlocks(int n) {
4        // Modulo to keep results within int range and avoid overflow.
5        const int kMod = 1e9 + 7;
6
7        // Accumulated sum of all block products.
8        long long ans = 0;
9
10        // Starting integer of the current block.
11        int start = 1;
12
13        // Iterate over each block; block i contains i consecutive integers.
14        for (int i = 1; i <= n; ++i) {
15            // Product of the i integers in the current block.
16            long long product = 1;
17
18            // Multiply integers from 'start' to 'start + i - 1'.
19            for (int j = start; j < start + i; ++j) {
20                product = product * j % kMod;
21            }
22
23            // Add this block's product to the running total.
24            ans = (ans + product) % kMod;
25
26            // Advance the start to the first integer of the next block.
27            start += i;
28        }
29
30        return static_cast<int>(ans);
31    }
32};
33

1/**
2 * Computes the sum of the products of consecutive integer blocks, modulo 1e9 + 7.
3 *
4 * The integers 1, 2, 3, ... are partitioned into blocks where:
5 *   - Block 1 contains 1 number,
6 *   - Block 2 contains 2 numbers,
7 *   - Block i contains i numbers,
8 * and the numbers are taken in increasing order.
9 *
10 * For each block, the product of its numbers is computed, and all block
11 * products are summed together.
12 *
13 * @param n The number of blocks to process.
14 * @returns The sum of block products modulo 1e9 + 7.
15 */
16function sumOfBlocks(n: number): number {
17    const MOD = 1_000_000_007;
18
19    // `blockStart` is the first integer of the current block.
20    let blockStart = 1;
21
22    // `answer` accumulates the sum of all block products.
23    let answer = 0;
24
25    // Iterate over each block from 1 to n; block `i` contains `i` integers.
26    for (let i = 1; i <= n; i++) {
27        // `blockProduct` holds the product of the integers in the current block.
28        let blockProduct = 1;
29
30        // Multiply the `i` consecutive integers starting at `blockStart`.
31        for (let value = blockStart; value < blockStart + i; value++) {
32            blockProduct = (blockProduct * value) % MOD;
33        }
34
35        // Add this block's product to the running total.
36        answer = (answer + blockProduct) % MOD;
37
38        // Advance the start index to the beginning of the next block.
39        blockStart += i;
40    }
41
42    return answer;
43}
44

Time and Space Complexity

Time Complexity: O(n^2)

The outer loop runs from i = 1 to n, so it executes n times. For each iteration i, the inner loop runs from k to k + i, meaning it performs exactly i iterations. Therefore, the total number of operations is 1 + 2 + 3 + ... + n = n(n+1)/2, which simplifies to O(n^2).
Space Complexity: O(1)

The algorithm only uses a constant number of variables (ans, mod, k, x, i, j), regardless of the input size n. No additional data structures that scale with n are allocated, so the space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Applying the modulo too late (or forgetting it entirely on the product)

The most common mistake is computing each block's product without applying the modulo at every multiplication, and only taking the modulo when adding to the total:

# WRONG: product is allowed to grow unbounded
for value in range(start, start + block_size):
    product = product * value          # no modulo here!
total = (total + product) % MOD        # modulo applied too late

Why it's a problem:

In languages with fixed-width integers (C++, Java, Go, etc.), the product overflows a 64-bit integer very quickly — even a handful of blocks produces values far larger than 2^63. The result silently wraps around and becomes incorrect.
In Python, integers are arbitrary precision, so the answer stays correct, but the unbounded products become enormous. Multiplying multi-thousand-digit numbers is slow, turning an otherwise manageable computation into a performance bottleneck.

Solution: Apply the modulo at every multiplication so each intermediate value stays bounded below 10^9 + 7:

for value in range(start, start + block_size):
    product = (product * value) % MOD   # modulo every step

This keeps each operand small (a product of two numbers < 10^9 + 7 fits comfortably in 64 bits), which is both correct and fast.

Pitfall 2: Mismanaging the `start` pointer between blocks

A second frequent error is incorrectly advancing the pointer that tracks where each block begins. Two typical variants:

# WRONG: resetting start, so every block begins at 1
for block_size in range(1, n + 1):
    start = 1                  # bug: should persist across iterations
    ...

# WRONG: advancing by the wrong amount
start += 1                     # bug: should advance by block_size

Why it's a problem:

The blocks are defined to consume consecutive integers, each block picking up exactly where the previous one left off. Resetting start makes every block reuse the integers 1, 2, 3, ...; advancing by 1 instead of block_size causes the blocks to overlap. Both yield the wrong sum.

Solution: Initialize start = 1 once before the loop, and after finishing block i advance it by exactly the number of integers consumed:

start += block_size            # exactly block_size integers were used

Pitfall 3: Initializing the product to `0` instead of `1`

product = 0                    # WRONG: anything multiplied by 0 is 0
for value in range(start, start + block_size):
    product = (product * value) % MOD

Why it's a problem: The product is built up via repeated multiplication, so the identity element must be 1. Starting at 0 forces every block's product to 0, making F(n) always 0.

Solution: Initialize product = 1 at the start of each block, since 1 is the multiplicative identity. Note this is distinct from total, which is built by addition and therefore correctly starts at 0.

Pitfall 4: Off-by-one in the range bounds

# WRONG: produces block_size + 1 integers
for value in range(start, start + block_size + 1):
    ...

Why it's a problem: Block i must contain exactly i integers. Using start + block_size + 1 as the upper bound includes one extra integer, while start + block_size - 1 omits one. Both shift every subsequent block and corrupt the sum.

Solution: Use range(start, start + block_size). Because Python's range is half-open (excludes the upper bound), this yields precisely block_size integers: start, start + 1, ..., start + block_size - 1.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering