分析

本质上是找到从高位到低位遍历的第一个奇数数字，假设该数字为a，其后接着的数字为$x_1, x_2,…,x_n$，则将$a, x_1, x_2, …, x_n$：
- 向上转变为 $(a+1), 0, …, 0$（共n个0）
- 或 向下转变为$a-1, 8, …, 8$（共n个8）。

注意当a为9时，只能向下转变。

时间复杂度分析：O(K), K为N的十进制位数。

C++ 代码

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

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    string n;
    cin >> n;
    bool flag = false;
    for (int i = 0; i < n.size(); i++) {
      if ((n[i] - '0') % 2 == 1) {
        if (i == n.size() - 1) {
          cout << "Case #" << t << ": " << 1 << endl;
        } else {
          string raw = n.substr(i + 1);
          long long temp = atoll(raw.c_str());
          string cmp = "";
          for (int i = 0; i < raw.size(); i++) cmp += "4";
          long long cmp_temp = atoll(cmp.c_str());
          if (temp > cmp_temp && n[i] - '0' != 9) {
            string up_str = "1";
            while (up_str.size() != raw.size() + 1) {
              up_str += "0";
            }
            long long up = atoll(up_str.c_str());
            // cout << "up" << temp << " " << up << endl;
            cout << "Case #" << t << ": " << up - temp << endl;
          } else {
            string low_str = "";
            while (low_str.size() != raw.size()) {
              low_str += "1";
            }
            long long low = atoll(low_str.c_str());
            // cout << "low" << temp << " " << low << endl;
            cout << "Case #" << t << ": " << temp + low + 1 << endl;
          }
        }

        flag = true;
        break;
      }
    }
    if (!flag) cout << "Case #" << t << ": " << 0 << endl;
  }
}