Skip to content

Latest commit

 

History

History
223 lines (180 loc) · 4.79 KB

README_EN.md

File metadata and controls

223 lines (180 loc) · 4.79 KB
comments difficulty edit_url rating source tags
true
Medium
1369
Weekly Contest 401 Q2
Array
Math
Combinatorics
Prefix Sum
Simulation

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

Python3

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]

Java

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

C++

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

Go

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

TypeScript

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