3179. Find the N-th Value After K Seconds LeetCode Solution
In this guide, you will get 3179. Find the N-th Value After K Seconds LeetCode Solution with the best time and space complexity. The solution to Find the N-th Value After K Seconds problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the N-th Value After K Seconds
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
Complexity Analysis
Time Complexity: O(n + k)
Space Complexity: O(n + k)
3179. Find the N-th Value After K Seconds LeetCode Solution in C++
class Solution {
public:
int valueAfterKSeconds(int n, int k) {
const auto [fact, invFact] = getFactAndInvFact(n + k - 1);
return nCk(n + k - 1, n - 1, fact, invFact);
}
private:
static constexpr int kMod = 1'000'000'007;
pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
vector<long> fact(n + 1);
vector<long> invFact(n + 1);
vector<long> inv(n + 1);
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return {fact, invFact};
}
int nCk(int n, int k, const vector<long>& fact, const vector<long>& invFact) {
return fact[n] * invFact[k] % kMod * invFact[n - k] % kMod;
}
}; /* code provided by PROGIEZ */
3179. Find the N-th Value After K Seconds LeetCode Solution in Java
class Solution {
public int valueAfterKSeconds(int n, int k) {
final long[][] factAndInvFact = getFactAndInvFact(n + k - 1);
final long[] fact = factAndInvFact[0];
final long[] invFact = factAndInvFact[1];
return nCk(n + k - 1, n - 1, fact, invFact);
}
private static final int kMod = 1_000_000_007;
private long[][] getFactAndInvFact(int n) {
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
long[] inv = new long[n + 1];
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return new long[][] {fact, invFact};
}
private int nCk(int n, int k, long[] fact, long[] invFact) {
return (int) (fact[n] * invFact[k] % kMod * invFact[n - k] % kMod);
}
} // code provided by PROGIEZ
3179. Find the N-th Value After K Seconds LeetCode Solution in Python
class Solution:
def valueAfterKSeconds(self, n: int, k: int) -> int:
return math.comb(n + k - 1, n - 1) % 1_000_000_007 # code by PROGIEZ
