Đếm số duy nhất có thể tạo từ N bằng cách cộng 1 và loại bỏ số 0 đuôi trong C++

Chúng ta được cho một số N làm đầu vào. Thực hiện hai phép toán trên N và xác định số lượng số duy nhất được tạo ra trong quá trình. Các bước sẽ là:

Cộng 1 vào số
Loại bỏ các số 0 đuôi từ số được tạo, nếu có

Nếu N là 8 thì các số được tạo sẽ là:

Áp dụng bước 1: 8 → 9 →

Áp dụng bước 2: 1 → (loại bỏ 0 từ 10)

Áp dụng bước 1: 2 → 3 → 4 → 5 → 6 → 7 → 8 (cùng chuỗi)

Số lượng số duy nhất sẽ là 9.

Ví dụ

Đầu vào

N=21

Đầu ra

Số lượng số duy nhất tạo từ N bằng cộng 1 và xóa số 0 đuôi là: 18

Giải thích

Các số sẽ là: 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 ---bây giờ chuỗi lặp lại. Số duy nhất: 18

Đầu vào

N=38

Đầu ra

Số lượng số duy nhất tạo từ N bằng cộng 1 và xóa số 0 đuôi là: 11

Giải thích

Các số sẽ là: 38, 39, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4 ---bây giờ chuỗi lặp lại. Số duy nhất: 11

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ tạo một unordered_set<int> U_S chứa tất cả các số duy nhất được tạo sau khi áp dụng bước 1 và 2. Trong trường hợp các số lặp lại, thì chúng ta sẽ dừng lặp. Kích thước của tập hợp sẽ cho chúng ta số lượng số duy nhất được tạo trong quá trình.

Nhận số N làm số nguyên.
Lấy unordered_set<int> U_S để chèn các số được tạo.
Hàm unique_N(unordered_set<int>& U_S, int N) nhận tập hợp và N và thêm số vào tập hợp U_S cho đến khi tất cả các số đều duy nhất trong nó.
Nếu U_S.count(N) trả về 1 có nghĩa N đã tồn tại trong tập hợp. Vì vậy các số sẽ lặp lại, trả về từ hàm.
Ngược lại chèn N vào tập hợp và áp dụng phép toán 1 (tăng 1).
Kiểm tra xem số N có số 0 đuôi không (là bội của 10).
Nếu N % 10 là 0, thì loại bỏ số 0 đuôi bằng cách chia nó cho 10.
Gọi hàm unique_N() với N cập nhật.
Sau khi trả về từ hàm, lấy biến đếm là kích thước của tập hợp U_S.
In kết quả là biến đếm.

Ví dụ mã

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

void unique_N(unordered_set<int>& U_S, int N) {
    if (U_S.count(N)) {
        return;
    }
    
    U_S.insert(N);
    N = N + 1;
    
    while (N % 10 == 0) {
        N = N / 10;
    }
    
    unique_N(U_S, N);
}

int main() {
    int N = 7;
    unordered_set<int> U_S;
    unique_N(U_S, N);
    int count = U_S.size();
    cout << "Số lượng số duy nhất tạo từ N bằng cộng 1 và xóa số 0 đuôi là: " << count;
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số lượng số duy nhất tạo từ N bằng cộng 1 và xóa số 0 đuôi là: 9