解答と解説: Pow

「問題演習: Pow」の解答編です。問題出題ページの最後に、下記の 3 点について考えるように提案しました。このような質問は実際の面接時に聞かれますので、これらを考えた上で解答例を見てください。

• O(n) より小さい時間計算量で解けますか。
• 入力が 0 の場合に対応していますか。
• 負の入力にも対応していますか。

解答例

Javaでの解答例です。

解説

上記の解答のポイントを順に述べます。

計算量

私の経験からすると下記のようなプログラムを書いた方が多くいると思います。これは n 回 pow メソッドを呼び出すので時間計算量は O(n) です。

一方、上記の私の解答では一度の処理で処理を半分に減らすことができるので、時間計算量は O(logn) です。logn は 2 を底とする対数です。つまり、一度目に pow メソッドが呼ばれたときに exponent の値を半分にして再度 pow メソッドを呼び出します。次に再度 pow メソッドを呼び出すときに exponent の値はさらに半分になります。

O(logn) は O(n) より小さいので、O(logn) の解答の方が優れています。補足しておくと、exponent が 2 で割り切れない場合は、pow(base, exponent / 2) を計算した後に base を一回だけ掛けることによって、辻褄を合わせています。

入力が 0 のとき

0 の値も忘れずに処理しましょう。exponent が 0 の時の解は常に 1 です。また、base が 0 の時は 0 を返します。

入力が負の値のとき

問題文に負の場合を除く旨が明示されていない限り、負の値も考慮に入れましょう。面接官に口頭で確認すると良いです。むしろこのようなディスカッションが面接の評価対象になりますので、積極的に質問する方が良いです。

係数が負の値の時は、例えば 2 の -3 乗 は 1 /8 ですので、先に正の値の計算結果を計算し 1 で割ります。

（上級者向け）exponent が Integer.MIN_VALUE のとき

これは思いつかなくても問題ないのですが、面白い内容なので記載しておきます。

Integer.MIN_VALUE は -2147483648 ですが、実は -1 を掛けても値は変わりません。つまり「Integer.MIN_VALUE * -1 = Integer.MIN_VALUE」です。

私の解答では exponent < 0 のとき、1 / pow(base, -exponent) を返していますが、もし exponent に Integer.MIN_VALUE が入っていた場合、無限ループになってしまいます。これを防ぐために exponent が Integer.MIN_VALUE の場合だけ pow(base, -exponent + 1) を計算した結果に対し base を 1 回掛けることによって辻褄を合わせています。

以上が解答となります。

余談ですが、この問題は数学的に解くと O(1)、つまり入力値の値に寄らない時間計算量で解けるようです。興味ある人は Java での実装をご覧ください。面接ではここまでは聞かれないので安心してください。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。