C++で桁の置き換え後の2つの数値の最大和と最小和を求める方法

問題概要

2つの正の整数 num1 と num2 が与えられます。この問題の目標は、両方の数値に対して桁(数字)の置き換えを行った後に実現できる最小の合計値と最大の合計値を求めることです。

たとえば、num1 が 434、num2 が 324 であり、「3 を 4 に置き換える」「4 を 3 に置き換える」ことが許されている場合を考えてみましょう。

• 最小の合計：333 + 323 = 656(すべての 4 を 3 に置き換える)
• 最大の合計：444 + 424 = 864(すべての 3 を 4 に置き換える)

入力例と出力例

例1

入力：

num1=3224 num2=4321

出力：

Maximum sum is : 8645
Minimum sum is : 6544

説明：4 は 3 より大きいため、すべての 3 を 4 に置き換えると両方の数値が大きくなります。num1 は 4224 に、num2 は 4421 となり、合計は 8645 です。逆に、3 は 4 より小さいため、すべての 4 を 3 に置き換えると両方の数値が小さくなります。num1 は 3223 に、num2 は 3321 となり、合計は 6544 です。

例2

入力：

num1=3111 num2=4111

出力：

Maximum sum is : 8222
Minimum sum is : 6222

説明：すべての 3 を 4 に置き換えると、num1 は 4111、num2 は 4111 となり、合計は 8222 です。すべての 4 を 3 に置き換えると、num1 は 3111、num2 は 3111 となり、合計は 6222 です。

プログラムのアプローチ

このプログラムでは、以下の手順で最小和と最大和を計算しています。

• 2つの数値は変数 num1 と num2 に格納されています。
• 関数 calculateSum(int n1, int n2) が、桁の置き換え後の最小和と最大和を計算する役割を担います。
• この関数は n1 と n2 を引数として受け取り、結果を minSum および maxSum に保存して表示します。
• まず、replace(n1, 4, 3) と replace(n2, 4, 3) を呼び出して、両方の数値に含まれるすべての 4 を 3 に置き換えます。
• 置き換え後の num1 と num2 を加算して最小和を求めます。
• 同様に、replace(n1, 3, 4) と replace(n2, 3, 4) を呼び出して、すべての 3 を 4 に置き換え、最大和を計算します。

replace関数の仕組み

• 関数 replace(int x, int digit1, int digit2) は、x に含まれるすべての digit1 を digit2 に置き換えた新しい数値を返します。
• 変数 number は新しく生成される数値を保持し、0 で初期化されます。
• temp は各反復ごとに 10 倍される桁の重み(乗数)です。
• x を 10 で割った余りを rem に格納することで、下の桁から順に 1 桁ずつ取り出します。
• rem が digit1 と一致した場合は digit2 に置き換え、number = number + digit2 * temp として加算します。
• 一致しない場合はそのまま number = number + rem * temp とします。
• x を 10 で割って次の桁へ進み、temp を 10 倍します(temp = temp * 10)。
• 最後に、完成した数値 number を返します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// digit1 を digit2 に置き換える関数
int replace(int x, int digit1, int digit2){
    int number = 0;
    int temp = 1;
    while (x > 0){
        int rem = x % 10;
        // 対象の桁が見つかったら置き換える
        if (rem == digit1)
            number = number + digit2 * temp;
        else
            number = number + rem * temp;
        temp *= 10;
        x = x / 10;
    }
    return number;
}
void calculateSum(int n1, int n2){
    // 4 を 3 に置き換えて最小和を求める
    int num1=replace(n1,4,3);
    int num2=replace(n2,4,3);
    int minSum=num1+num2;
    // 3 を 4 に置き換えて最大和を求める
    num1=replace(n1,3,4);
    num2=replace(n2,3,4);
    int maxSum=num1+num2;
    std::cout << "Minimum Sum by digit replacement: " << minSum;
    std::cout << "\nMaximum Sum by digit replacement: " << maxSum;
}
int main(){
    int num1 = 3131, num2 = 4141;
    calculateSum(num1, num2);
    return 0;
}

実行結果

Minimum Sum by digit replacement: 6262
Maximum Sum by digit replacement: 8282

まとめ

このアルゴリズムは、数値を文字列として扱わずに剰余演算と除算だけで各桁を処理する点が特徴です。計算量は各数値の桁数に比例する O(d)(d は桁数)となり、非常に効率的です。「小さい数字への置き換えで最小和」「大きい数字への置き換えで最大和」というシンプルな発想により、全パターンを試すことなく答えを一度で求められます。