完全平方数のチェック
どんな順序付きリストでもバイナリサーチ(2分探索)を行うことができます。たとえば、昇順に並べられた身長のリスト、整数のリスト、浮動小数点数のリストなどに適用できますし、整数の集合 や自然数の集合 、有理数の集合 に対しても同じです。いずれにしても、解になり得る範囲を設定し、各反復で必要のない部分を除外していく手順は変わりません。
チャレンジ
与えられた正の整数
n について、sqrt 関数を使わずに n が完全平方数(“full square”)かどうかを判定してください。入力
入力は単一の整数
n (2 ≤ n ≤ ) です。出力
n が完全平方数であれば
Yes、そうでなければ No を出力してください。例
入力 | 出力 |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
ヒント
もし
n が完全平方数であるならば、ある整数 x が存在して となります。したがって [1, 2, …, n] の範囲から x を探す方法を考えてみてください。Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB