Đếm số lượng số nhị phân nhỏ hơn N trong C++

Cho một số nguyên N làm đầu vào. Mục tiêu là tìm số lượng các số nguyên nhỏ hơn N và được biểu diễn dưới dạng nhị phân (chỉ chứa các chữ số 0 và 1). Ví dụ: nếu N = 12 thì các số nhỏ hơn 12 là 1, 10, 11 là các số nhị phân và chứa các chữ số 0 và 1. Đáp án sẽ là 3.

Ví dụ

Đầu vào

N=100

Đầu ra

Số lượng số nhị phân nhỏ hơn N là: 4

Giải thích

Các số nhị phân nhỏ hơn 100 là: 1, 10, 11, 100

Đầu vào

N=120

Đầu ra

Số lượng số nhị phân nhỏ hơn N là: 7

Giải thích

Các số nhị phân nhỏ hơn 120 là: 1, 10, 11, 100, 101, 110, 111

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

Trong phương pháp này, chúng ta sẽ sử dụng một vector nguyên vec. Đầu tiên, chúng ta đẩy số 1 vào vector. Để tạo ra số nhị phân tiếp theo, chúng ta lấy số cuối cùng (temp) từ vec (ban đầu là 1). Sau đó tạo số tiếp theo bằng: temp*10 và temp*10+1 vì các số nhị phân sẽ luôn là (1, 10, 11, 100, 110, 111...). Lấy các số từ vec và nếu nó nhỏ hơn N thì tăng biến đếm.

• Nhận số nguyên N làm đầu vào.
• Hàm Smaller_N(int N) nhận N và trả về số lượng các số nhị phân nhỏ hơn N.
• Khởi tạo biến đếm ban đầu là 0.
• Tạo vector nguyên vec để lưu trữ các số chỉ chứa 0 và 1.
• Thêm 1 vào vector bằng vec.push_back(1).
• Sử dụng vòng lặp while, duyệt vec và lấy phần tử cuối cùng là temp = vec.back(). Và xóa nó khỏi vec.
• Nếu temp <= N, thì tăng biến đếm và tạo số nhị phân tiếp theo là temp*10 và temp*10+1 và thêm vào vec.
• Cuối cùng của vòng while, trả về biến đếm làm kết quả.

Ví dụ mã

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

int Smaller_N(int N) {
    int count = 0;
    vector<int> vec;
    vec.push_back(1);
    
    while (!vec.empty()) {
        int temp = vec.back();
        vec.pop_back();
        
        if (temp <= N) {
            count++;
            int temp_2 = temp * 10;
            vec.push_back(temp_2);
            vec.push_back(temp_2 + 1);
        }
    }
    
    return count;
}

int main() {
    int N = 1000;
    cout << "Số lượng số nhị phân nhỏ hơn N là: " << Smaller_N(N);
    return 0;
}

Đầu ra

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

Số lượng số nhị phân nhỏ hơn N là: 8