Skip to main content

Find the N-th Value After K Seconds

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

Examples​

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

Solution for Find the N-th Value After K Seconds Problem​

Approach​

The problem essentially involves calculating the prefix sum of an array iteratively over a given number of seconds K. Each element in the array represents a value that is derived from summing up all previous elements in the array (including itself) from the previous iteration. The goal is to determine the value of the N-th element in the array after K seconds.

Steps​

  • Start with an array of size N where all elements are initialized to 1. This represents the array at time t=0.
  • For each second from 1 to K, update the array by calculating the prefix sum for each element. This means that each element at position i (0-indexed) will be updated to the sum of all elements from position 0 to i of the previous iteration.
  • After K seconds, return the value of the N-th element in the array.

Implementation​

Live Editor
function Solution(arr) {
   function valueAfterKSeconds(n, k) {
    let arr = new Array(n).fill(1);
    const mod = 1000000007;

    for (let i = 1; i <= k; i++) {
        let prefix = new Array(n).fill(0);
        prefix[0] = arr[0] % mod;
        for (let j = 1; j < n; j++) {
            prefix[j] = (prefix[j - 1] + arr[j]) % mod;
        }
        arr = prefix;
    }
    return arr[n - 1];
}
  const input = 4;
  const  k = 5
  const output = valueAfterKSeconds(input , k) ;
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(N∗K)O(N*K) because of Nested Loops
  • Space Complexity: O(N)O(N) because of prefix array

Code in Different Languages​

Written by @hiteshgahanolia
 function valueAfterKSeconds(n, k) {
let arr = new Array(n).fill(1);
const mod = 1000000007;

for (let i = 1; i <= k; i++) {
let prefix = new Array(n).fill(0);
prefix[0] = arr[0] % mod;
for (let j = 1; j < n; j++) {
prefix[j] = (prefix[j - 1] + arr[j]) % mod;
}
arr = prefix;
}
return arr[n - 1];
}

References​