今回は、前回と同じ問題を、多重ループを使った解き方で挑戦してみる！
問題のテーマが二重ループだから王道の解き方なのかな？
問題概要
N! を 2 で何回割ることができるか？
入力例：
4
出力例：
3
🧭 方針：二重ループ
素直に 1 × 2 × … × (N-1) × N を計算してから 2 で割ろうとすると、かけ算の計算結果が巨大な数となってしまいオーバーフローする(´;ω;｀)
そこで、次の性質を利用🚀
2 は素数であるので、1 × 2 × … × (N-1) × N を 2 で割ることができる回数は、
(1 を 2 で割ることができる回数) + (2 を 2 で割ることができる回数) + … + (N-1 を 2 で割ることができる回数) + (N を 2 で割ることができる回数) と一致する。
よって、
「1 〜 N の各値について 2 で割ることのできる回数を調べ、それらの和を求める。」
「1 〜 N の各値について」についてはループ処理で行うことができ、
「2 で割ることのできる回数を調べる」処理は、「ループ変数が 2 で割り切れる場合、2 で割る。」という処理を繰り返すことでおこなうことができる！
このようにして、二重ループで解くことができる✨
❌ NGコード例:
const rl = require('readline').createInterface({input:process.stdin});
rl.once('line', (input) => {
const N = Number(input);
let count = 0;
for (let i = 1; i <= N; i++){
if(i % 2 === 0){
for(let temp = i; temp > 0; temp /= 2, count++);
}
}
console.log(count);
rl.close();
});
❌ 問題点：
if(i % 2 === 0){ で 偶数しか処理していないので、
「すでに 2 で割れることは保証されている」＝最初の1回はOK。
しかし、例えば6の場合2で割り切れるので処理を始めると、一回目は2で割り切れるが、商は３になり、３は割り切ることができないから❌
▶️ つまり、初めは偶数でも割っていくと、奇数になる場合もあるということ。
✅ 修正版：OK例
const rl = require('readline').createInterface({input:process.stdin});
rl.once('line', (input) => {
const N = Number(input);
let count = 0;
for (let i = 1; i <= N; i++){
if(i % 2 === 0){
for(let temp = i; temp % 2 === 0; temp /= 2, count++);
}
}
console.log(count);
rl.close();
});
(let temp = i; temp % 2 === 0; temp /= 2, count++)
によって、「ループ変数が 2 で割り切れる場合、2 で割る。」という処理を繰り返し、その度にカウントしている。
🗒️ まとめ
各数ごとに2で割る方が理解しやすい印象だけど、前回のコードの方が計算に無駄がない感じがする。