Doubling Plus Carry — Solution & Editorial

Back to the Problem

The process is a linear recurrence; exponentiate its 2×2 companion matrix.

Complexity: O(log N)