Find the N-th Value After K Seconds
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We maintain an array representing the state a at each second. We start with an array of n ones. Then, for k seconds, we repeatedly update the array by calculating the prefix sum of the current array.
Algorithm
- Define a constant
MODas10^9 + 7. - Create an integer array
aof sizen. - Initialize all elements of
ato1. - Loop
ktimes, representing the seconds from1tok. - Inside the loop, iterate from
i = 1ton-1:- Update
a[i]by adding the value of the preceding element:a[i] = (a[i] + a[i-1]) % MOD.
- Update
- After the loops complete, the value at
a[n-1]is the final answer.
Walkthrough
The most straightforward way to solve this problem is to follow the simulation step-by-step. We begin with an array a of size n, where every element is 1. The problem states that after each second, every element a[i] is updated to be the sum of all preceding elements plus itself. This is equivalent to calculating the prefix sum of the array.
We can perform this simulation for k seconds. In each second, we can update the array in-place. The new value of a[i] is the sum of the old values from a[0] to a[i]. This can be calculated more efficiently as new_a[i] = new_a[i-1] + old_a[i]. Since we iterate from left to right, a[i-1] will already hold its new value for the current second. Thus, the update rule simplifies to a[i] = a[i] + a[i-1] for i > 0.
We repeat this process k times. All additions are performed modulo 10^9 + 7 to prevent integer overflow. After k iterations, a[n-1] will hold the required value.
class Solution { public int valueAfterKSeconds(int n, int k) { int MOD = 1_000_000_007; int[] a = new int[n]; java.util.Arrays.fill(a, 1); // Simulate for k seconds for (int second = 0; second < k; second++) { // Update the array to its prefix sum for (int i = 1; i < n; i++) { a[i] = (a[i] + a[i-1]) % MOD; } } return a[n - 1]; }}Complexity
Time
O(k * n) - We have a nested loop. The outer loop runs `k` times, and the inner loop for calculating prefix sums runs `n-1` times.
Space
O(n) - We use an array of size `n` to store the values at each second.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem statement.
Sufficiently efficient for the given constraints (
n, k <= 1000).
Cons
Less efficient than the mathematical approach, with a quadratic time complexity.
Might be too slow if the constraints on
norkwere larger.
A more efficient approach involves recognizing a mathematical pattern in the generated values. The values in the array after each second correspond to entries in Pascal's triangle, which can be represented by binomial coefficients. The value of a[i] after t seconds is C(i+t, t). This transforms the simulation problem into a combinatorial one: calculating C(n+k-1, k) modulo 10^9 + 7.
Algorithm
- Identify that the value of
a[i]aftertseconds,a_t[i], follows the pattern of a binomial coefficient:a_t[i] = C(i+t, t). - The required value is
a_k[n-1], which translates toC(n-1+k, k)orC(n+k-1, n-1). - The problem is now to compute
C(N, K) % MODwhereN = n+k-1,K = k, andMOD = 10^9 + 7. - Use the formula
C(N, K) = N! / (K! * (N-K)!). - To compute this modulo a prime, we use modular inverse:
C(N, K) ≡ N! * (K!)^-1 * ((N-K)!)^-1 (mod MOD). - Precompute factorials up to
NmoduloMODto getN!,K!, and(N-K)!efficiently. - Calculate the modular inverse of
(K! * (N-K)!)using Fermat's Little Theorem, which involves modular exponentiation:a^(MOD-2) ≡ a^-1 (mod MOD). - Multiply the numerator
N!with the modular inverse of the denominator to get the final result.
Walkthrough
By observing the array's state after a few seconds, we can deduce a mathematical formula. Let a_t[i] be the value at index i after t seconds.
a_0[i] = 1 = C(i, 0)a_1[i] = i+1 = C(i+1, 1)a_2[i] = (i+1)(i+2)/2 = C(i+2, 2)
This pattern can be proven by induction using the hockey-stick identity (sum_{j=r to n} C(j, r) = C(n+1, r+1)). The general formula is a_t[i] = C(i+t, t). We need to find a_k[n-1], which is C((n-1)+k, k) = C(n+k-1, k).
To compute C(N, K) % MOD for a prime MOD, we can use the formula C(N, K) = N! / (K! * (N-K)!). In modular arithmetic, this becomes (N! * modInverse(K!) * modInverse((N-K)!)) % MOD. Since 10^9 + 7 is prime, we can find the modular inverse using Fermat's Little Theorem: a^(MOD-2) ≡ a^-1 (mod MOD). We can implement this using modular exponentiation (also known as binary exponentiation).
To make the calculation efficient, we can precompute factorials up to N = n+k-1.
class Solution { private static final int MOD = 1_000_000_007; public int valueAfterKSeconds(int n, int k) { if (k == 0) return 1; // We need to calculate C(n + k - 1, k) mod MOD int N = n + k - 1; // Precompute factorials up to N long[] fact = new long[N + 1]; fact[0] = 1; for (int i = 1; i <= N; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // C(N, k) = N! / (k! * (N-k)!) long numerator = fact[N]; long denominator = (fact[k] * fact[N - k]) % MOD; // Modular inverse of denominator using Fermat's Little Theorem long invDenominator = power(denominator, MOD - 2); return (int) ((numerator * invDenominator) % MOD); } // Modular exponentiation to calculate (base^exp) % MOD private long power(long base, int exp) { long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; } return res; }}Complexity
Time
O(n + k) - Precomputing factorials takes O(n+k) time. Modular exponentiation takes O(log(MOD)). The overall complexity is dominated by the factorial computation.
Space
O(n + k) - We need an array of size `n+k-1` to store the precomputed factorials.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it much faster than simulation.
Scales well even for larger values of
nandk.
Cons
Requires mathematical insight to recognize the combinatorial pattern.
Implementation is more complex, involving modular inverse and modular exponentiation.
Solutions
Solution
class Solution {public int valueAfterKSeconds(int n, int k) { final int mod = (int)1 e9 + 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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.