Skip to content

3792. Sum of Increasing Product Blocks πŸ”’

Description

You are given an integer n.

A sequence is formed as follows:

  • The 1st block contains 1.
  • The 2nd block contains 2 * 3.
  • The ith block is the product of the next i consecutive integers.

Let F(n) be the sum of the first n blocks.

Return an integer denoting F(n) modulo 109 + 7.

 

Example 1:

Input: n = 3

Output: 127

Explanation:​​​​​​​

  • Block 1: 1
  • Block 2: 2 * 3 = 6
  • Block 3: 4 * 5 * 6 = 120

F(3) = 1 + 6 + 120 = 127

Example 2:

Input: n = 7

Output: 6997165

Explanation:

  • Block 1: 1
  • Block 2: 2 * 3 = 6
  • Block 3: 4 * 5 * 6 = 120
  • Block 4: 7 * 8 * 9 * 10 = 5040
  • Block 5: 11 * 12 * 13 * 14 * 15 = 360360
  • Block 6: 16 * 17 * 18 * 19 * 20 * 21 = 39070080
  • Block 7: 22 * 23 * 24 * 25 * 26 * 27 * 28 = 5967561600

F(7) = 6006997207 % (109 + 7) = 6997165

 

Constraints:

  • 1 <= n <= 1000

Solutions

Solution 1: Simulation

We can directly simulate the product of each block and accumulate it to the answer. Note that since the product can be very large, we need to take the modulo at each step of the calculation.

The time complexity is \(O(n^2)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def sumOfBlocks(self, n: int) -> int:
        ans = 0
        mod = 10**9 + 7
        k = 1
        for i in range(1, n + 1):
            x = 1
            for j in range(k, k + i):
                x = (x * j) % mod
            ans = (ans + x) % mod
            k += i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int sumOfBlocks(int n) {
        final int mod = (int) 1e9 + 7;
        long ans = 0;
        int k = 1;
        for (int i = 1; i <= n; ++i) {
            long x = 1;
            for (int j = k; j < k + i; ++j) {
                x = x * j % mod;
            }
            ans = (ans + x) % mod;
            k += i;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOfBlocks(int n) {
        const int mod = 1e9 + 7;
        long long ans = 0;
        int k = 1;
        for (int i = 1; i <= n; ++i) {
            long long x = 1;
            for (int j = k; j < k + i; ++j) {
                x = x * j % mod;
            }
            ans = (ans + x) % mod;
            k += i;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func sumOfBlocks(n int) (ans int) {
    const mod int = 1e9 + 7
    k := 1
    for i := 1; i <= n; i++ {
        x := 1
        for j := k; j < k+i; j++ {
            x = x * j % mod
        }
        ans = (ans + x) % mod
        k += i
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function sumOfBlocks(n: number): number {
    const mod = 1000000007;
    let k = 1;
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        let x = 1;
        for (let j = k; j < k + i; j++) {
            x = (x * j) % mod;
        }
        ans = (ans + x) % mod;
        k += i;
    }
    return ans;
}

Comments