JavaScriptで合計と最大公約数(GCD)から元の2つの数値を求める方法

問題

2つの引数を受け取るJavaScript関数を作成する必要があります。1つ目の引数はある2つの数値の合計(sum)を、2つ目の引数はその2つの数値の最大公約数(GCD:HCF)を表します。

関数の目的は、これらの条件を満たす元の2つの数値を見つけ出し、配列として返すことです。

考え方(アプローチ)

2つの数値の最大公約数が gcd であるとき、その2つの数値はどちらも必ず gcd の倍数になります。したがって、合計も必ず gcd の倍数でなければなりません。

この性質を使うと、処理は次のようにシンプルにまとめられます。

• sum % gcd !== 0 の場合(合計がGCDで割り切れない場合)、条件を満たす数値のペアは存在しないため -1 を返します。
• 割り切れる場合は、一方の数値を gcd 自体とし、もう一方を sum - gcd とします。sum - gcd も gcd の倍数であるため、このペアの最大公約数は確かに gcd となり、条件を満たします。

このアルゴリズムは剰余演算を1回行うだけで済むため、時間計算量はO(1)と非常に効率的です。

コード例

const sum = 12;
const gcd = 4;
const findNumbers = (sum, gcd) => {
    const res = [];
    if (sum % gcd !== 0){
        return -1;
    }else{
        res.push(gcd);
        res.push(sum - gcd);
        return res;
    };
};
console.log(findNumbers(sum, gcd));

出力結果

[4, 8]

出力の検証

上記の例では、合計が12、最大公約数が4という条件に対して [4, 8] が返されています。

• 合計:4 + 8 = 12 ✓
• 最大公約数:gcd(4, 8) = 4 ✓

このように、返された2つの数値は与えられた条件を正しく満たしていることが確認できます。