Can you find an efficient solution to this problem?

Question

Given the following recurrence relation:

C(0) = 0
C(n) = (C(n-1) + c * int(C(n-1) < u)) - u    // the int function converts a boolean to an integer.

Constraints: 0 <= u <= c

Can you find an efficient solution for finding the first n(>= 1) (if it exists) for which C(n) = 0? If no such n exists, return -1

If such n exists, a brute force approach is to loop from one to infinity, calculating C(n) and returning that n if it's 0. We could remember the value for C(n-1) for each iteration so we don't recalculate it.

Answer 1

Intuitively, the function increases by c - u steadily until it reaches or exceeds u, where u is subtracted from the current value and the process repeats.

The first thing to notice is that when the "steps back" by u, it does so in a periodic fashion. The value after subtracting u for the first time will be k * (c - u) - u, where the integer k corresponds to the previous iteration number. This value, modulo (c - u) is congruent to -u. This gives the "stagger" each time we "step back": -u mod (c - u).

Next, we want to find how many times we need to "step back" in our sequence before we hit zero. That's essentially asking how many times we "stagger" the sequence before it all cancels out. In the worst case (that is, our step size and stagger are coprime), this is equal to our step size (c - u). If our step size and the stagger -u may share a common factor, we must divide out this factor. This means the number of times we "step back" in our sequence is: (c - u) // gcd(c - u, stagger).

Now, we need to count to total number of steps in the sequence. The number of times the sequence increases between backsteps is not constant- it will vary between up to two different values (by +/- 1). However, we can calculate the total number of steps a different way, by expressing the value of the function in terms of value added by forward-steps minus the value subtracted by the backsteps: fstep * (c - u) - bstep * u. If we solve this for forward steps, and add to the backstep count, we get the total number of steps, or in other words, the value of n where C(n) equals 0.

Of course, if c == u, the result is 1. We can immediately return this to avoid division/modulo by zero.

Putting this into (python) code:

from math import gcd

def solve(u, c):
    if c == u:
        return 1

    stagger = (-u) % (c - u)
    backsteps = (c - u) // gcd(c - u, stagger)
    steps = backsteps + backsteps * u // (c - u)
    return steps

I've tested this implementation against a naive brute-force solution for about 20 thousand randomly chosen (u, c) pairs ranging in value in the thousands, and the results match exactly. I have high confidence in its correctness.

Regarding efficiency- the slowest part is the GCD computation, which time complexity is O(log(c)^2), so overall its going to be pretty fast and scale well.