Addition chains

CodeChefRating 3340Open on judge ↗

An addition chain for a positive integer N is a sequence of positive integers C = (A0, A1, ..., AL) such that - 1 = A0 1 L – 1 L = N, - for each i such that 1 ≤ i ≤ L there exist integers j and k such that 0 ≤ j, k and Ai = Aj + Ak. The integer L is called the length of the chain C. For example, C = (1, 2, 3, 6, 12, 15) is an addition chain of length 5 for N = 15. Indeed, A0 = 1,

HINT LADDERno hints yet

L1 Observation

L2 Technique

L3 Approach

L4 Pseudo-code

🔒

L5 Full solution

L5 unlocks only if you insist twice

solution.cppC++17

CodeSearch Tutor

Hints, not spoilers — it won’t hand over the full solution unless you insist.

voice by Sarvam AI