Chênh lệch lớn nhất từ thay đổi chữ số (Max Difference You Can Get From Changing an Integer) trong C++

Cho số nguyên num. Thực hiện đúng 2 lần: chọn chữ số x, thay tất cả x bằng y (0-9, y có thể = x). Kết quả không được dẫn đầu bằng 0 và không được = 0. Tìm max(|a - b|) với a, b là kết quả 2 lần.

Ví dụ

Đầu vào: 555
Đầu ra: 888 (a=999 thay 5→9, b=111 thay 5→1).

Thuật toán tham lam

• Tối đa hóa (getMax): Tìm chữ số đầu tiên ≠ 9 từ trái sang, thay tất cả chữ số đó thành 9.
• Tối thiểu hóa (getMin):
  • Nếu chữ số đầu ≠ 1: thay tất cả chữ số đầu thành 1.
  • Nếu chữ số đầu = 1: tìm chữ số đầu tiên > 1 (từ trái sang, bỏ qua 0,1), thay tất cả chữ số đó thành 0.
  • Trường hợp đặc biệt: số chỉ có 1 chữ số và là 1 → trả về 1.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int getMax(int x) {
        string s = to_string(x);
        char target = '9';
        for (char c : s) if (c != '9') { target = c; break; }
        for (char& c : s) if (c == target) c = '9';
        return stoi(s);
    }
    int getMin(int x) {
        string s = to_string(x);
        if (s[0] != '1') {
            char target = s[0];
            for (char& c : s) if (c == target) c = '1';
        } else {
            if (s.size() == 1) return 1;
            char target = 0;
            for (int i = 1; i < s.size(); ++i)
                if (s[i] > '1') { target = s[i]; break; }
            if (target) for (char& c : s) if (c == target) c = '0';
        }
        return stoi(s);
    }
public:
    int maxDiff(int num) {
        return abs(getMax(num) - getMin(num));
    }
};

Độ phức tạp

• Thời gian: O(log num) - độ dài chuỗi số.
• Không gian: O(log num) - chuỗi trung gian.

Kết quả kiểm thử

Đầu vào: 666
Đầu ra: 888