Loại bỏ chữ số 9 trong C++

Mô tả bài toán

Cho một số nguyên n, hãy trả về số nguyên thứ n sau khi thực hiện thao tác sau: Bắt đầu từ số nguyên 1, loại bỏ mọi số nguyên chứa chữ số 9 (như 9, 19, 29...). Lúc này ta có dãy số nguyên mới: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ... Lưu ý rằng 1 là số nguyên đầu tiên.

Ví dụ: Nếu đầu vào là 9, đầu ra sẽ là 10.

Ý tưởng giải pháp

Bài toán này thực chất là chuyển đổi số n từ cơ số 10 sang cơ số 9, sau đó coi kết quả như một số trong cơ số 10. Cụ thể:

• Khởi tạo ret = 0 (kết quả), s = 1 (hệ số vị trí).
• Khi n > 0:
  • ret += (n % 9) * s
  • n /= 9
  • s *= 10
• Trả về ret.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int newInteger(int n) {
        int ret = 0;
        lli s = 1;
        while (n) {
            ret += (n % 9) * s;
            n /= 9;
            s *= 10;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.newInteger(120);
    return 0;
}

Đầu vào

120

Đầu ra

143