Skip to content

3179. Find the N-th Value After K Seconds

SourceWeekly Contest 401 Q2DifficultyMediumRating1369

Description

You are given two integers n and k.

Initially, you start with an array a of n integers where a[i] = 1 for all 0 <= i <= n - 1. After each second, you simultaneously update each element to be the sum of all its preceding elements plus the element itself. For example, after one second, a[0] remains the same, a[1] becomes a[0] + a[1], a[2] becomes a[0] + a[1] + a[2], and so on.

Return the value of a[n - 1] after k seconds.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 4, k = 5

Output: 56

Explanation:

Second State After
0 [1,1,1,1]
1 [1,2,3,4]
2 [1,3,6,10]
3 [1,4,10,20]
4 [1,5,15,35]
5 [1,6,21,56]

Example 2:

Input: n = 5, k = 3

Output: 35

Explanation:

Second State After
0 [1,1,1,1,1]
1 [1,2,3,4,5]
2 [1,3,6,10,15]
3 [1,4,10,20,35]

 

Constraints:

  • 1 <= n, k <= 1000

Solutions

Solution 1: Simulation

Thinking

Each second every entry becomes a prefix sum. The closed form is \(\binom{n+k-1}{n-1}\), but \(n,k\le 1000\) makes a direct simulation simpler under a modulus.

The array length stays \(n\), so prefix sums can be written in place from the left.

Start from all ones, repeat \(a[i]+=a[i-1]\) modulo \(10^9+7\) for \(k\) seconds, and return \(a[n-1]\).

We notice that the range of the integer \(n\) is \(1 \leq n \leq 1000\), so we can directly simulate this process.

We define an array \(a\) of length \(n\) and initialize all elements to \(1\). Then we simulate the process for \(k\) seconds, updating the elements of array \(a\) every second until \(k\) seconds have passed.

Finally, we return \(a[n - 1]\).

The time complexity is \(O(n \times k)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(a\).

1
2
3
4
5
6
7
8
class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        a = [1] * n
        mod = 10**9 + 7
        for _ in range(k):
            for i in range(1, n):
                a[i] = (a[i] + a[i - 1]) % mod
        return a[n - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int valueAfterKSeconds(int n, int k) {
        final int mod = (int) 1e9 + 7;
        int[] a = new int[n];
        Arrays.fill(a, 1);
        while (k-- > 0) {
            for (int i = 1; i < n; ++i) {
                a[i] = (a[i] + a[i - 1]) % mod;
            }
        }
        return a[n - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        const int mod = 1e9 + 7;
        vector<int> a(n, 1);
        while (k-- > 0) {
            for (int i = 1; i < n; ++i) {
                a[i] = (a[i] + a[i - 1]) % mod;
            }
        }
        return a[n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func valueAfterKSeconds(n int, k int) int {
    const mod int = 1e9 + 7
    a := make([]int, n)
    for i := range a {
        a[i] = 1
    }
    for ; k > 0; k-- {
        for i := 1; i < n; i++ {
            a[i] = (a[i] + a[i-1]) % mod
        }
    }
    return a[n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function valueAfterKSeconds(n: number, k: number): number {
    const a: number[] = Array(n).fill(1);
    const mod: number = 10 ** 9 + 7;
    while (k--) {
        for (let i = 1; i < n; ++i) {
            a[i] = (a[i] + a[i - 1]) % mod;
        }
    }
    return a[n - 1];
}

Comments