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?

  • \$\begingroup\$ My personal insight: leetcode, hackerrank and this types of platforms don't teach you any good habits. Most of the solutions presented by users use single letter variables, no type hints, classes defined for sake of classes (famous "Solution") and many more. Second thing is to get good you have to literally grind, it's not like somebody just sat down and came up with a solution. They studied most common algos first, then saw 100 of ready solutions and then came up with 101 on their own. After some training most of the problems turn out to be schematic. \$\endgroup\$
    – Gameplay
    Sep 21 at 18:08
  • \$\begingroup\$ You see a graph? Bang cpy-paste implementation of bfs or dfs and add a single if statement in the right place. Sorted list...think binary search. Non-overlapping subproblems DP and so on. Funny thing is though it's good to know this stuff in general, but I haven't met a single engineer who had a real need of implementing e.g. quicksort in their career, I've met some who like to flex on the fact they can 😄 Persistence is the key if you want to get good imho and don't listen to bs of people who say "it's easy". Sure it is for them, cause they spent hours on it or learned a few algos by heart \$\endgroup\$
    – Gameplay
    Sep 21 at 18:18

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.