We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the N-th Value After K Seconds

Difficulty: Medium

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. Return the value of a[n - 1] after k seconds, modulo 10^9 + 7.

Key Insights

  • The initial state of the array is filled with 1s.
  • Each second, the elements of the array are updated based on the prefix sums.
  • The updates can be seen as building the cumulative sums iteratively.
  • The final element of the array after k seconds can be derived from the patterns observed in the cumulative sums.

Space and Time Complexity

Time Complexity: O(n * k)
Space Complexity: O(n)

Solution

The problem can be solved by simulating the updates to the array for k seconds. We will maintain the array and update it in each iteration by calculating the prefix sums. The final result will be stored in a[n - 1], and since the result can be large, we will take it modulo 10^9 + 7.

Code Solutions

def find_nth_value(n, k):
    MOD = 10**9 + 7
    a = [1] * n  # Initialize the array with all 1s
    
    for _ in range(k):
        for j in range(1, n):
            a[j] = (a[j - 1] + a[j]) % MOD  # Update each element based on the prefix sum
    
    return a[n - 1]  # Return the last element after k seconds
← Back to All Questions