C++で整数の桁を変更して得られる最大差を求める方法

問題概要

整数 num が与えられます。この整数に対して、次の手順をちょうど2回適用することを考えます。

• 0〜9の範囲から数字 x を1つ選ぶ。
• 同じく0〜9の範囲から別の数字 y を1つ選ぶ(y は x と同じでも構いません)。
• num の10進表現に含まれるすべての x を y に置き換える。ただし、新しい整数に先頭ゼロが含まれてはならず、値が0になってもいけません。

1回目の操作結果を a、2回目の操作結果を b としたとき、a と b の差の最大値を求めるのがこの問題の目的です。

たとえば入力が 555 の場合、出力は 888 になります。1回目は x = 5、y = 9 を選んで結果を a に格納し、2回目は x = 5、y = 1 を選んで結果を b に格納します。

すると a = 999、b = 111 となり、最大差は 999 − 111 = 888 です。

解法の考え方

この問題は「1回目の操作でできるだけ大きな数を、2回目の操作でできるだけ小さな数を作り、その差を取る」という方針で解けます。具体的には、次の2つの補助関数を実装します。

getMax():最大値を作る関数

1. 数値 x を文字列 s に変換する。
2. 先頭から順に走査し、最初に現れる「9」以外の桁を見つける。
3. その桁をすべて「9」に置き換える。
4. 文字列を数値に戻して返す。

すでにすべての桁が9である場合を除き、この操作で必ず数値を最大化できます。

getMin():最小値を作る関数

1. 数値 x を文字列 s に変換する。
2. 先頭の桁が「1」でない場合:先頭の桁と同じ数字をすべて「1」に置き換える。先頭を0にすると先頭ゼロ違反となるため、置き換え先として選べる最小の数字は「1」だからです。
3. 先頭の桁が「1」である場合:
   ・文字列の長さが1なら 1 をそのまま返す。
   ・そうでなければ、2文字目以降で最初に現れる「1」より大きい桁を見つけ、その桁をすべて「0」に置き換える。
4. 文字列を数値に戻して返す。

メイン処理の流れ

• a = getMax(num) を計算する。
• b = getMin(num) を計算する。
• |a − b| を返す。

C++実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int getMax(int x){
        string s = to_string(x);
        char a = '9';
        int i = 0;
        while (i < s.size() && s[i] == '9')
            i++;
        if (i < s.size())
            a = s[i];
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == a) {
                s[i] = '9';
            }
        }
        return stoi(s);
    }
    int getMin(int x){
        string s = to_string(x);
        char a;
        if (s[0] != '1') {
            a = s[0];
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == a) {
                    s[i] = '1';
                }
            }
        }
        else {
            if (s.size() == 1) {
                return 1;
            }
            int i = 0;
            a = '1';
            while (i < s.size() && s[i] <= '1')
                i++;
            if (i < s.size())
                a = s[i];
            for (int i = 1; i < s.size(); i++) {
                if (s[i] == a) {
                    s[i] = '0';
                }
            }
        }
        return stoi(s);
    }
    int maxDiff(int num) {
        int a = getMax(num);
        int b = getMin(num);
        return abs(a - b);
    }
};
main(){
    Solution ob;
    cout << (ob.maxDiff(666));
}

入力

666

出力

888

まとめ

入力 666 の場合、getMax() は最初に現れる「6」を「9」に置き換えて 999 を作り、getMin() は「6」を「1」に置き換えて 111 を作ります。したがって最大差は 999 − 111 = 888 となります。このように、桁の置き換えルールを工夫すれば、桁数に比例した計算量(O(n))で効率的に答えを求められます。先頭ゼロや値0の禁止といった制約への対応が、getMin() の分岐処理のポイントです。