C++で与えられた整数が3の累乗かどうかを判定する方法

この問題では、整数Nが与えられ、その整数が3の累乗であるかどうかを判定することが課題となります。

問題の例

具体的な例を見てみましょう。

入力 : N = 729
出力 : Yes

説明：

36 = 729

729は3の6乗に等しいため、3の累乗であると判定できます。

解法のアプローチ

この問題を効率的に解くには、3の累乗の性質を利用します。ポイントとなるのは、32ビット符号付き整数で表現できる最大の3の累乗は 1162261467（3¹⁹） であるという点です。

判定方法は非常にシンプルです。与えられた数Nが 1162261467 を割り切れるかどうか を確認します。もしNが3の累乗であれば、その約数はすべて3の累乗（1, 3, 9, 27, ...）であるため、必ず余りが0になります。逆に、余りが0でなければNは3の累乗ではありません。

この手法の利点は、ループや再帰を使わずにたった1回の剰余演算（O(1)）で判定できることです。

実装例

この解法をC++で実装したプログラムが以下です。

#include <iostream>
using namespace std;

bool isPowerOf3(int n){
    if (n <= 0)
        return false;
    return 1162261467 % n == 0;
}

int main(){
    int n = 27;
    if (isPowerOf3(n))
        cout << "The number is a power of 3";
    else
        cout << "The number is not a power of 3";
    return 0;
}

出力結果

The number is a power of 3

解説

コードの動作を詳しく見てみましょう。

• 負の数と0の除外： n ≤ 0 の場合は false を返します。3の累乗は常に正の数だからです。
• 剰余による判定： 1162261467 % n == 0 が成立すれば、n は 3¹⁹ の約数であり、すなわち3の累乗です。
• 計算量： ループ不要のため、時間計算量はO(1)、空間計算量もO(1)と非常に効率的です。

上記の例では n = 27 は 3³ に等しいので、「The number is a power of 3」と出力されます。