解答と解説: Power of Two

「問題演習: Power of Two」の解答編です。この問題は様々な解法がありますので、それぞれの解の導き方を見ていきましょう。

解答例

Javaでの解答例です。

解答１）


解答２）


解答３）

解説

2 の累乗は 1, 2, 4, 8, 16, 32... のような数字です。2 の累乗を 2 で割り続けると最後に 1 が残ります。この特徴を利用した解法が解答１になります。問題文から最も直感的に導くことができる解法です。ループを回るごとに n の値は半分になるので、時間計算量は O(logn) です。

解答２では 2 の累乗を 2 進数で表現したとき、1 となるビットが 1 つしか存在しない点に注目しています。例えば、下記の 0 ~ 5 の 10 進数を 2 進数で表現した場合を見ると1, 2, 4 の時は 1 が 1 つしか存在しないことがわかると思います。この特徴を利用してビットが 1 になる回数が 1 つのときに true を返しています。この解法もループを回るごとに n の値は半分になるので、時間計算量は O(logn) です。

• 0: 0
• 1: 1
• 2: 10
• 3: 11
• 4: 100
• 5: 101

解答３は、知らなくても良いですが Java には Integer.bitCount(int n) というメソッドが用意されています。このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。解答２で説明したように 2 の累乗はビットが 1 になる回数が 1 回という特徴を利用します。n の値によらずに 1 度で解が求まるので、時間計算量は O(1) です。

解答１と２で示した方法で解ければ問題ないのですが、面接官によっては他の解き方が思いつくか聞いてくることもあります。もちろん思いついた方が良いので、日頃から 1 つの解き方だけでなく、他の解法も探す習慣をつけると良いと思います。

実は他にも解法はいくつかあります。難しいですが少し考えてみてください。英語版の Wikipedia に他の解法が載っています。リンクはこちら。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。