นับจำนวนที่สามารถทำให้เป็นกำลังสองได้โดยการบวก 1 ใน C++

ได้รับอาร์เรย์จำนวนเต็มบวก ต้องการนับจำนวนที่เป็นกำลังสองอยู่แล้ว หรือจะกลายเป็นกำลังสองได้หากบวก 1 เข้าไป (สูงสุด 1 ครั้ง)

แนวทาง

ใช้ log2 ตรวจสอบ: ถ้า floor(log2(x)) == ceil(log2(x)) แสดงว่า x เป็นกำลังสอง

ตรวจสอบทั้งตัวเลขเดิมและตัวเลข+1

ตัวอย่าง

อินพุต: arr[] = {1, 3, 2, 5, 6}

เอาต์พุต: 3

คำอธิบาย: 1+1=2 (2¹), 3+1=4 (2²), 2=2¹ → 3 ตัว

อินพุต: arr[] = {2, 4, 8, 16}

เอาต์พุต: 4 (เป็นกำลังสองทุกตัว)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
#include <math.h>
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 {
            ++arr[i];
            if (floor(log2(arr[i])) == ceil(log2(arr[i]))) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {5, 6, 9, 3, 1};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << endl << "Count of numbers with power of 2 possible: " << powofTwo(Arr, len);
    return 0;
}

ผลลัพธ์

Count of numbers with power of 2 possible: 2