きままにものづくり

日々の気付いたことなんかを書いてます。

SRM596Div1Easy

問題

サイズNの配列が与えられる。同じサイズですべての要素が0である配列から始め、与えられた配列と同じにするのに必要な最小操作回数を求めよ。
許される操作は以下の2つである。

  • ある要素を選び1を足す
  • すべての要素に2をかける

解法

2進数で表記した際にbitがセットされている数を数える。2で割っていき、セットされているビットの数を数えることで、答えが求まる。

計算量

 O(N log V)
N:要素数
V:最大値

コード