Leetcode: 2327. Number of People Aware of a Secret and Problem with programming skill in general

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 that out of 365 discussions, only 13 are tagged with "recursive" or "recursion".

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

how to deal with this incompetency and how to fix it as a software engineer?

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, math, etc. the same output and end result and pattern.

why is that?

Reread the materials, tried to think, put a lot of time on it, but no help.

Answer 1

It sounds like you're not happy with the solutions you're coming up with. Even when they work they aren't fast enough to make you happy. Keep demanding perfection and you're sure to maintain your discontent.

But I wonder if maybe I've noticed a little something that you might like to know about:

Python is not tail call optimized.

That doesn't mean you can't write recursive programs in Python. It just means you're very likely to have better memory performance if you convert such programs to their iterative form.

If performance is important to you then you'll need to master a host of odd little facts like that before you'll be squeezing the last drop of performance out of your CPU (or is that GPU? So many details).

Answer 2

There are a number of skills/techniques/experiance that will help with Leetcode style problems, specifically:

• Being able to switch between imperative and functional (recursive) forms - sometimes one form makes the solution more obvious.
• Knowing where to memoize effectively, in recursive form its usually fairly obvious (to avoid the recursion) - it's less obvious in imperative form.
• Being able to recognize when it's possible to switch from a recursive memoized form to tabulation.

---

However in this case the solution is hiding in the wording of the problem.

Imagine we changed the problem from a "secret" to a "disease"

• The delay is how long after catching the disease the person becomes infectious.
• The forget is the delay (after catching) before the person is cured.
• A person is infectious after the delay until they are cured.
• "Knowing the secret" = "Total caught" - "Total cured".

Once stated this way, it becomes clear that the number we really need to track is the number of infectious people since that determines how many new people are infected each iteration.

An optimization we could use is a circular buffer since we can forget about cured people once we have accounted for them.

Finally the number (10**9 + 7) is a very odd choice - why did the question author pick it? Most likely it is prime - as a result, it is likely you can use it in the loop to avoid overflowing an Int type.

---

Summary: When you look at enough problems, everything I have said here starts to jump out at you - it's just practice.

Answer 3

I'm trying to provide an intuitive answer to your intuitive question here, because you're not asking how to solve the problem but rather why recursion is not the favored way of doing so.

Let's explore a different example. Feel free to skip to the horizontal separator when you catch my drift.

Compound interest is an interest example here. You put $100 into an account with 2% annual compound interest. It's easy to know what to expect next year: $102. However, due to the compound nature of the interest, the progression is not linear. The next years it won't be $104, $106, ... because you're forgetting to add the part of this year's interest that you get on the money that was last year's interest.

If you are algorithmically inclined, but not mathematically, your response to this problem will be something along the lines of:

Wait a minute. I can't decide once what every year's interest is going to be. I can only decide what year N's interest is going to be after I know what year (N-1)'s interest was!

I'm sidestepping the fact that the above logic can be written using an iteration regardless of whether it's recursive or not. Recursion is not the focus of this particular analogy.

The end result here is that a developer who is not mathematically inclined will come up with something like:

public decimal CalculateCompoundInterest(decimal startingMoney, decimal interestRate, int years)
{
    var currentMoney = startingMoney;

    for(int i = 1; i <= years; i++)
        currentMoney *= (1 + interestRate);

    return currentMoney;
}

While this isn't wrong, the mathematically inclined will understand that you can use exponentiation here to avoid recursion.

This leads to a Big O optimization. The above code needs to iterate N times. If you want to calculate what it looks like in a billion years, you need to iterate a billion times.

But the mathematically inclined will see that this can be done in a single go by doing:

    return startingMoney * Math.Pow(1 + interestRate, years);

---

The above example is a long-winded way of saying "there's probably a computationally less complex way of doing this".

The same kind of exponentiation is at play here. You're thinking of tracking each individual line of "who told who". Your recursive structure ensures that you retain awareness of who revealed what to who. However, this doesn't matter for the problem at hand. The answer you're asking to provide doesn't care who told who.

Instead of building a two-dimensional nested graph, it would suffice to have a one-dimensional list of "people who know the secret" (provided that you track their knowledge expiry). It doesn't matter whether C and D were told the secret by A and B (respectively), all that matters is that there were 2 people who knew the secret when it was time to pass it on, and therefore now there's 4 people who know the secret.

Breaking down the relation between who told who allows you to simplify the process. Instead of needing to track individuals, you can track a count of people. This removes a dimension from the complexity, leading to a less computationally complex calculation overall.

It's not about whether recursion is correct or not - it can be correct. But it's not the only way to deconstruct the problem, and because it's not the most efficient, people tend not to use that as their final approach.

Answer 4

Recursion is bad if a recursive formula calculates the same result repeatedly. An awful example is the naive recursive algorithm to evalue Fibonacci numbers: To calculat F(n), you calculate F(n-1) and F(n-2). For that you calculate F(n-2), F(n-3) twice, and F(n-4). For that you calculate F(n-3), F(n-4) three times, F(n-5) three times, and F(n-6) and so on. You end up calculating F(2) for example gazillion times.

Recursion is quite reasonable for Quicksort, for example. There's the problem that there might be very deep recursion, which you handle by sorting the smaller partition recursively, and the larger one in a loop. Here the only problem is a slight overhead due to many function calls (it doesn't matter that they are recursive).

Recursion is very, very reasonable for problems where the recursion saves you from rearranging the problem in a complicated way.

Now in your case, you seem to evaluate the same values repeatedly, but you use the "memoization" trick: Every time you evaluated a value of the function, you store it, so another call trying to get the same result does practically no work. That trick would work wonders for the Fibonacci problem. Without that you'd probably be stuck forever.