B - Happy Number Editorial
by
spheniscine
Let \(f(x)\) represent the result of applying the given operation once to the integer \(x\). Note that the maximum value \(f(x)\) could take for \(x \le 2026\) is \(f(1999) = 244\), therefore we could conclude the set of positive integers \(\le 2026\) is closed under \(x \mapsto f(x)\).
We could therefore just do the operation repeatedly and trace the history of values encountered, if we reach \(1\) we report yes, otherwise if we find one of the values we’ve already encountered, we’d be trapped in a cycle, therefore we report no.
Let \(S = 2026\) be the size of the closed set. We could keep the history in an array-list and check it via linear search and it would take \(O(S^2)\) and be fast enough. We could also solve it in \(O(S)\) using a hash set or a boolean array.
posted:
last update:
