# 3179. Find the N-th Value After K Seconds

## 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

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$.

• 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];
}
}

• 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];
}
};

• 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]


• 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]
}

• 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];
}