B - Happy Number 解説
by
spheniscine
Let \(f(x)\) represent the result of applying an 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.
投稿日時:
最終更新:
