Math and Geometry
Repetition, and how to notice it
A process that must either stop or repeat, and two ways to tell which.
Key idea
The argument you already know
A process that repeatedly transforms a value, where the value stays within a finite range, must eventually revisit a value it has seen. From there it repeats forever.
That is the same finiteness argument as Unit 7's array-as-linked-list problem. The consequence is that any such process either reaches a target or enters a cycle, and there is no third outcome.
So the algorithm is: run the process, and stop when you either hit the target or detect repetition.
Below is the transformation itself, followed by the sequence it produces from 2, run far enough for the repeat to be visible.
Tip
Why the values stay in a finite range
The transformation cannot grow without limit. For a three-digit number the largest possible result is three times 81, which is 243, and every larger input shrinks quickly into that range.
That bound is what makes the finiteness argument apply. Stating it, rather than asserting that a cycle must occur, is the difference between an argument and a hope.
Key idea
Detecting the cycle without a set
The set costs memory proportional to the cycle length. The fast-and-slow pointers from Unit 7 detect the same repetition in constant space, with the transformation playing the role of the next pointer.
It is exactly the same code with a function call in place of a field access. Recognizing that the technique was never about linked lists is the point.
Gotcha
The two pointers must start apart
Starting both at the same value makes the loop condition true immediately and the function returns before doing anything. The fast one is advanced once before the loop for exactly that reason.
The same detail appeared in Unit 7. It is the kind of thing that produces a function returning the wrong answer on every input rather than an obvious error.
Key idea
Repeated squaring, a different use of repetition
A related idea: computing a power by repeated multiplication takes as many steps as the exponent. Squaring instead halves the exponent each step, so it takes about log of it.
Whether the exponent is odd decides whether one factor is peeled off first. Both the loop and the recursion are short; write whichever you can state the invariant for.
Below the exponent is halved down to nothing, with the odd steps marked. Those marks are exactly the binary digits of the exponent, which is what the technique really is.
Edge cases
Negative and zero exponents
A negative exponent inverts the base and flips the sign, which is one line at the top. A zero exponent returns one and the loop simply does not run.
In languages with fixed-width integers, negating the most negative value overflows and needs care. Python integers have no such limit, so the straightforward version is safe here, and saying that you know the difference is worth a sentence.
Predict the output: why the values cannot run away
The transformation squares each digit and adds the results. The largest value it can produce from an input of a given length is worked out. Type the three lines it prints.
Happy Number
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Powx N
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.