Bulb Switcher หาจำนวนหลอดไฟที่เปิดอยู่หลัง n รอบใน C++

มีหลอดไฟ n ดวง ปิดทั้งหมด รอบที่ 1: เปิดทุกดวง รอบที่ 2: ปิดทุก 2 ดวง รอบที่ i: สลับทุก i ดวง รอบที่ n: สลับดวงสุดท้าย หาจำนวนหลอดที่เปิดอยู่หลัง n รอบ

ตัวอย่าง: n=3 → 1 ดวง (ลำดับ: [on,on,on] → [on,off,on] → [on,off,off])

วิธีแก้ปัญหา (Mathematical Insight: Perfect Squares)

หลอดไฟสลับสถานะเมื่อรอบเป็นตัวหารของหมายเลขหลอด

หลอดเปิดอยู่ = มีตัวหารจำนวนคี่ = เลขยกกำลังสอง (perfect squares)

จำนวน = ⌊√n⌋

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

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

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

int main() {
    Solution ob;
    cout << ob.bulbSwitch(3);
    return 0;
}

Input

3

Output

1