LeetCode 3792 - Sum of Increasing Product Blocks

Difficulty: 🟡 Medium
Topics: Math, Simulation

Solution

Problem Understanding

The problem defines a sequence of blocks, where each block contains the product of a consecutive range of integers.

The pattern works as follows:

The 1st block contains only 1
The 2nd block contains 2 × 3
The 3rd block contains 4 × 5 × 6
The 4th block contains 7 × 8 × 9 × 10

Notice that every block uses the next consecutive integers without overlap. If the i-th block has length i, then the numbers used continue from where the previous block stopped.

We define F(n) as the sum of the first n blocks. The task is to compute this sum and return it modulo 10^9 + 7.

In other words, for each block:

Compute the product of its assigned consecutive integers.
Add that product to the running total.
Return the final sum modulo 10^9 + 7.

The input consists of a single integer n, which represents how many blocks we need to include in the sum.

The output is a single integer representing:

$$F(n) = \text{block}_1 + \text{block}_2 + \cdots + \text{block}_n$$

under modulo 10^9 + 7.

The constraints tell us that:

1 <= n <= 1000

This is relatively small, which means even a quadratic solution may be acceptable. However, we still need to be careful because the products grow extremely quickly. Without modular arithmetic, numbers become enormous very fast. Since the answer is required modulo 10^9 + 7, we should apply the modulo operation during multiplication and addition to avoid overflow and unnecessary large integer computations.

An important observation is that the total amount of work is not n, but rather the total number of integers across all blocks:

$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$

For n = 1000, this equals 500,500, which is still manageable.

Some important edge cases include:

n = 1, where only the first block exists and the answer is simply 1.
Large n values such as 1000, where products become astronomically large if modulo arithmetic is not used during multiplication.
Correctly continuing consecutive integers between blocks, since an off-by-one mistake can easily produce incorrect products.

Approaches

Brute Force Approach

A direct brute-force solution follows the problem statement literally.

We maintain a current integer that tracks the next unused number. For each block i, we multiply the next i consecutive integers together to compute the block product. Then we add that block product to the final answer.

For example, if we are computing block 4, we multiply:

$$7 \times 8 \times 9 \times 10$$

because the previous blocks already used 1 through 6.

This method is correct because it exactly simulates the process described in the problem. Every number is used once, every block contains the correct number of consecutive integers, and all block sums are accumulated.

The downside is that if we do not apply modulo during multiplication, intermediate values become extremely large. Also, recomputing everything naively could lead to unnecessary overhead.

Key Insight for the Optimal Approach

The important observation is that we do not need any advanced mathematics or memoization. Since the total number of multiplications is bounded by:

$$1 + 2 + \dots + n = O(n^2)$$

and n <= 1000, a careful simulation is already efficient enough.

The optimization is to apply modulo arithmetic at every multiplication and addition step. This prevents integer explosion and ensures computations stay efficient.

We keep a pointer current_number that always represents the next unused integer in the sequence. For each block:

Start with a product of 1
Multiply the next i integers
Add the result to the running sum
Continue to the next block

This achieves an efficient and clean solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Direct simulation, may suffer from huge intermediate numbers without modulo
Optimal	O(n²)	O(1)	Simulation with modulo applied during multiplication

Algorithm Walkthrough

Define a constant MOD = 10^9 + 7 because every operation must be performed modulo this value.
Initialize a variable answer = 0 to store the running sum of block products.
Initialize current_number = 1. This tracks the next unused integer that belongs to the next block.
Iterate through block sizes from 1 to n.
For each block size i, initialize block_product = 1.
Multiply the next i consecutive integers into block_product. After each multiplication:

Apply modulo MOD
Increment current_number

This ensures the next block starts exactly where the current one ended. 7. After computing the block product, add it to answer and again apply modulo MOD. 8. After all blocks are processed, return answer.

Why it works

The algorithm maintains an invariant that current_number always points to the next unused integer in the sequence. Since each block consumes exactly i integers for block i, and we increment current_number after every multiplication, the blocks always contain the correct consecutive numbers without overlap or omission. Because every multiplication and addition is performed modulo 10^9 + 7, the returned value matches the required modular result.

Python Solution

class Solution:
    def sumOfBlocks(self, n: int) -> int:
        MOD = 10**9 + 7
        
        answer = 0
        current_number = 1
        
        for block_size in range(1, n + 1):
            block_product = 1
            
            for _ in range(block_size):
                block_product = (
                    block_product * current_number
                ) % MOD
                current_number += 1
            
            answer = (answer + block_product) % MOD
        
        return answer

The implementation follows the algorithm directly.

We begin by defining the modulo constant 10^9 + 7. The variable answer stores the cumulative sum of block products, while current_number tracks the next unused integer.

For each block size from 1 to n, we initialize block_product to 1, since multiplication starts from the identity value.

Inside the nested loop, we multiply block_product by current_number, immediately apply modulo, and increment current_number so that the next integer is ready.

Once a block is fully computed, we add its contribution to answer, again taking modulo to keep numbers manageable.

Finally, after processing all blocks, we return the accumulated answer.

Go Solution

func sumOfBlocks(n int) int {
	const mod int = 1_000_000_007

	answer := 0
	currentNumber := 1

	for blockSize := 1; blockSize <= n; blockSize++ {
		blockProduct := 1

		for i := 0; i < blockSize; i++ {
			blockProduct = (blockProduct * currentNumber) % mod
			currentNumber++
		}

		answer = (answer + blockProduct) % mod
	}

	return answer
}

The Go implementation mirrors the Python approach closely.

One important difference is integer handling. Since multiplication occurs repeatedly, we rely on modulo reduction after every operation to keep values bounded. Because all intermediate values stay below 10^9 + 7, standard integer arithmetic is sufficient in Go for this problem.

The logic for tracking consecutive numbers and computing block products remains identical.

Worked Examples

Example 1

Input: n = 3

We process three blocks.

Block Size	Numbers Used	Block Product	Running Sum
1	`[1]`	1	1
2	`[2, 3]`	6	7
3	`[4, 5, 6]`	120	127

Step-by-step state:

Step	current_number	block_product	answer
Start	1	-	0
Block 1	2	1	1
Block 2	4	6	7
Block 3	7	120	127

Final result:

$$1 + 6 + 120 = 127$$

Example 2

Input: n = 7

Block Size	Numbers Used	Block Product	Running Sum
1	`[1]`	1	1
2	`[2, 3]`	6	7
3	`[4, 5, 6]`	120	127
4	`[7, 8, 9, 10]`	5040	5167
5	`[11, 12, 13, 14, 15]`	360360	365527
6	`[16, 17, 18, 19, 20, 21]`	39070080	39435607
7	`[22, 23, 24, 25, 26, 27, 28]`	5967561600	6006997207

Applying modulo:

$$6006997207 \bmod (10^9 + 7)$$

Result:

$$6997165$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Total multiplications equal `1 + 2 + ... + n = n(n+1)/2`
Space	O(1)	Only a few variables are maintained

Although there is a nested loop, the total amount of work is bounded by the triangular number:

$$\frac{n(n+1)}{2}$$

Since n <= 1000, at most 500,500 multiplications are required, which is very efficient.

Test Cases

solution = Solution()

assert solution.sumOfBlocks(1) == 1  # Minimum input
assert solution.sumOfBlocks(2) == 7  # First two blocks: 1 + 6
assert solution.sumOfBlocks(3) == 127  # Example 1
assert solution.sumOfBlocks(4) == 5167  # Adds 7*8*9*10
assert solution.sumOfBlocks(5) == 365527  # Medium-sized case
assert solution.sumOfBlocks(7) == 6997165  # Example 2
assert solution.sumOfBlocks(10) > 0  # Larger valid input
assert solution.sumOfBlocks(1000) >= 0  # Maximum constraint stress test

Test	Why
`n = 1`	Validates minimum boundary case
`n = 2`	Ensures consecutive block construction works
`n = 3`	Verifies Example 1
`n = 4`	Tests transition between blocks
`n = 5`	Validates cumulative correctness
`n = 7`	Verifies Example 2
`n = 10`	Tests larger iteration flow
`n = 1000`	Stress test for maximum constraint

Edge Cases

Minimum Input, `n = 1`

The smallest possible input contains only the first block. A buggy implementation might incorrectly initialize values or skip the first block entirely due to loop boundaries. Our implementation handles this naturally because the loop starts at block size 1, producing the correct answer of 1.

Large Products Causing Overflow

Products grow extremely quickly. Even for modest values of n, the multiplication results become enormous. A naive implementation that postpones modulo operations could suffer from integer overflow in languages with fixed-width integers. Our solution applies modulo immediately after every multiplication, ensuring values remain bounded.

Off-by-One Errors in Consecutive Numbers

A common bug is incorrectly advancing the sequence pointer, causing numbers to overlap or skip between blocks. For example, block 3 must begin exactly after block 2 ends. By maintaining a single current_number variable and incrementing it immediately after use, the implementation guarantees every integer appears exactly once in the correct order.