Đếm số có thể thành lũy thừa của 2 bằng cách cộng 1 trong C++

Cho mảng số nguyên dương. Mục tiêu đếm số lượng phần tử đã là lũy thừa của 2 HOẶC có thể trở thành lũy thừa của 2 bằng cách cộng thêm 1 (tối đa 1 lần).

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 3, 2, 5, 6}
• Output: 3
• Giải thích: 1+1=2 (2¹), 3+1=4 (2²), 2=2¹. Còn 5+1=6, 6+1=7 không phải lũy thừa của 2.

Ví dụ 2:

• Input: arr = {2, 4, 8, 16}
• Output: 4
• Giải thích: Tất cả đã là lũy thừa của 2.

Kiểm tra lũy thừa của 2

Số x là lũy thừa của 2 ⇔ log₂(x) là số nguyên ⇔ floor(log₂(x)) == ceil(log₂(x)).

Hoặc dùng thao tác bit: (x & (x-1)) == 0 (với x > 0) - nhanh và chính xác hơn.

Mã nguồn C++ (Sử dụng log2)

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

int powofTwo(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (floor(log2(arr[i])) == ceil(log2(arr[i]))) {
            count++;
        } else {
            int val = arr[i] + 1;
            if (floor(log2(val)) == ceil(log2(val))) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {5, 6, 9, 3, 1};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "So luong co the thanh luy thua 2: " << powofTwo(Arr, len);
    return 0;
}

Mã nguồn tối ưu (Sử dụng thao tác bit)

bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

int powofTwo_optimized(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (isPowerOfTwo(arr[i]) || isPowerOfTwo(arr[i] + 1)) {
            count++;
        }
    }
    return count;
}

Kết quả chạy chương trình

So luong co the thanh luy thua 2: 2

Độ phức tạp

• Thời gian: O(n) - duyệt mảng một lần.
• Không gian: O(1).

Lưu ý

• Phiên bản log2 có vấn đề độ chính xác số thực với số lớn.
• Phiên bản bitwise chính xác 100% và nhanh hơn đáng kể.
• Cần kiểm tra x > 0 trước khi dùng (x & (x-1)).