Leetcode: 2327. Number of People Aware of a Secret

Question

On day 1, one person discovers a secret.

You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.

Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 10**9 + 7.

this is how i solved the challenge with 889 ms of runtime and 17.5 MB of memory. and checked others and found out out of 365 discussions, only 13 are tagged with "recursive" or "recursion".

why i cant think like normal? is it lack of skill, knowledge, understanding, or cognitive deficit? note: have few years of experience in industry with cs background.

x = 6
n = 1
delay = 2
forget = 4
dp = [0 for _ in range(x+1)]

def f(n, x, delay, forget):
  if n > x:
    return 0

  if dp[n] != 0:
    return dp[n]

  t = 1
  for i in range(forget - delay):
    t += f(n+delay+i, x, delay, forget)

  if n + forget <= x:
    t -= 1

  c = (t % (10**9+7))
    
  dp[n] = c

  return c

this is how mostly others solved the challenge with 33 ms of runtime and 16.3 MB of memory.

def f(n, delay, forget):
  dp = [0] * n
  c = 0
  dp[0] = 1

  for i in range(1, n):
    dp[i] = c + dp[i-delay] - dp[i-forget]
    c = dp[i]

  return sum(dp[n-forget:]) % 1000000007

untill now, ive solved about 40 challenges and most of solutions(except a few) are bad in terms of runtime or memory or both. beside that, the energy and time it takes to solve such challenges is huge even for a simple challenge. aside from all these, the final code is very very messy.

in other areas like solving real world problems, the same output and end result and pattern.

why is that?

Answer 1

Your approach may be less efficient due to a recursive design that doesn't account for overlapping subproblems effectively, leading to suboptimal runtime and memory usage. The iterative solution optimizes by building up a dp array as it goes, eliminating the need for recursive calls.

def f(n, delay, forget):
  dp = [0] * (n + 1)
  dp[0] = 1
  total = 0
  
  for i in range(1, n + 1):
    dp[i] = (dp[i - 1] + total - (dp[i - forget] if i >= forget else 0)) % 1000000007
    if i >= delay:
      total = (total + dp[i - delay]) % 1000000007
  
  return (sum(dp[-forget:]) - dp[-1]) % 1000000007

Solving problems efficiently is a skill that improves with time, exposure to various algorithms, and understanding the underlying math and logic. It's not necessarily a cognitive deficit or lack of skill. Keep practicing and reviewing optimal solutions to improve.