Find the N-th Value After K Seconds
Find the N-th Value After K Seconds is a medium dynamic programming problem solved with the 2d dp pattern.
The best approach, optimal (binomial coefficient), runs in O(k + log p) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from simulation (prefix sums) up.
Problem
Start with an array a of n ones. Every second, all elements change at the same moment: each a[i] becomes the sum of the elements a[0] through a[i] as they were before that second.
After k seconds, return the value of the last element a[n - 1]. Because it can be huge, return it modulo 10^9 + 7.
Examples
Example 1
- Input
n = 3, k = 2- Output
6- Why
- [1, 1, 1] becomes [1, 2, 3] after one second and [1, 3, 6] after two.
Example 2
- Input
n = 1, k = 5- Output
1- Why
- A single element is always its own prefix sum, so it stays 1.
Example 3
- Input
n = 4, k = 3- Output
20- Why
- [1,1,1,1] → [1,2,3,4] → [1,3,6,10] → [1,4,10,20].
Constraints
1 <= n, k <= 1000- Return the answer modulo
10^9 + 7.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Simulation (prefix sums) | O(n · k) | O(n) |
| Optimal (binomial coefficient) | O(k + log p) | O(1) |
1Simulation (prefix sums)
O(n · k)k passes over n elements.O(n)One array of length n.Keep the array and apply the update k times. Updating left to right in place works because a[i] only needs the new a[i - 1] (which is already the prefix sum up to i - 1) plus its own old value.
- Fill a with n ones.
- Repeat k times: for i from 1 to n - 1, a[i] = (a[i] + a[i - 1]) mod 10^9 + 7.
- Return a[n - 1].
class Solution {
public int valueAfterKSeconds(int n, int k) {
final int MOD = 1_000_000_007;
int[] a = new int[n];
Arrays.fill(a, 1);
for (int s = 0; s < k; s++) {
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:
MOD = 10**9 + 7
a = [1] * n
for _ in range(k):
for i in range(1, n):
a[i] = (a[i] + a[i - 1]) % MOD
return a[n - 1]class Solution {
public:
int valueAfterKSeconds(int n, int k) {
const int MOD = 1000000007;
vector<int> a(n, 1);
for (int s = 0; s < k; s++) {
for (int i = 1; i < n; i++) {
a[i] = (a[i] + a[i - 1]) % MOD;
}
}
return a[n - 1];
}
};function valueAfterKSeconds(n, k) {
const MOD = 1000000007;
const a = new Array(n).fill(1);
for (let s = 0; s < k; s++) {
for (let i = 1; i < n; i++) {
a[i] = (a[i] + a[i - 1]) % MOD;
}
}
return a[n - 1];
}2Optimal (binomial coefficient)
O(k + log p)Two products of k terms plus one fast power with about 30 squarings.O(1)A few long variables.The value at index i after s seconds satisfies v(i, s) = v(i - 1, s) + v(i, s - 1) with ones on the borders, which is exactly the rule of Pascal's triangle. So v(n - 1, k) = C(n - 1 + k, k). Compute it as a product of k numerator terms divided by k!, using a modular inverse (Fermat's little theorem, since the modulus is prime).
- num = product of (n - 1 + i) for i = 1..k, mod p.
- den = k! mod p.
- Return num × den^(p - 2) mod p, using fast exponentiation.
class Solution {
private static final long MOD = 1_000_000_007L;
public int valueAfterKSeconds(int n, int k) {
long num = 1, den = 1;
for (int i = 1; i <= k; i++) {
num = num * ((n - 1 + i) % MOD) % MOD;
den = den * i % MOD;
}
return (int) (num * power(den, MOD - 2) % MOD);
}
private long power(long base, long exp) {
long result = 1;
base %= MOD;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
}class Solution:
def valueAfterKSeconds(self, n: int, k: int) -> int:
MOD = 10**9 + 7
num = 1
den = 1
for i in range(1, k + 1):
num = num * (n - 1 + i) % MOD
den = den * i % MOD
return num * pow(den, MOD - 2, MOD) % MODclass Solution {
static const long long MOD = 1000000007LL;
long long power(long long base, long long exp) {
long long result = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
public:
int valueAfterKSeconds(int n, int k) {
long long num = 1, den = 1;
for (int i = 1; i <= k; i++) {
num = num * ((n - 1 + i) % MOD) % MOD;
den = den * i % MOD;
}
return (int)(num * power(den, MOD - 2) % MOD);
}
};function valueAfterKSeconds(n, k) {
const MOD = 1000000007n;
const power = (base, exp) => {
let result = 1n;
base %= MOD;
while (exp > 0n) {
if (exp & 1n) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1n;
}
return result;
};
let num = 1n, den = 1n;
for (let i = 1; i <= k; i++) {
num = num * BigInt(n - 1 + i) % MOD;
den = den * BigInt(i) % MOD;
}
return Number(num * power(den, MOD - 2n) % MOD);
}Edge cases to test
- n = 1: the answer is always 1
- k = 1: the answer is n
- Large n and k: values overflow without taking the modulo at every step
Hints
Hint 1
Each second replaces the array by its prefix sums. Simulate it with one running sum per second.
Hint 2
Look at the table of values: it is Pascal's triangle turned on its side.
Hint 3
The last element after k seconds is the binomial coefficient C(n - 1 + k, k).
FAQ
What is the best time complexity for Find the N-th Value After K Seconds?
Optimal (binomial coefficient) runs in O(k + log p) time and O(1) extra space. Two products of k terms plus one fast power with about 30 squarings.
Which pattern does Find the N-th Value After K Seconds use?
It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.
Is there a brute force solution for Find the N-th Value After K Seconds?
Yes. Simulation (prefix sums) takes O(n · k) time and O(n) space. Keep the array and apply the update k times.
Which edge cases should I test for Find the N-th Value After K Seconds?
n = 1: the answer is always 1; k = 1: the answer is n; Large n and k: values overflow without taking the modulo at every step.