Giả sử ban đầu có n bóng đèn được nối tắt. Đầu tiên chúng tôi bật tất cả các bóng đèn. Sau đó, chúng tôi tắt mỗi bóng đèn thứ hai. Ở vòng thứ ba, chúng tôi bật tắt mọi bóng đèn thứ ba (bật nếu nó đang tắt hoặc tắt nếu nó đang bật). Tương tự, đối với vòng thứ i, chúng ta bật tắt mọi bóng đèn thứ i. Đối với vòng thứ n, chúng tôi chỉ bật tắt bóng đèn cuối cùng. Vậy ta phải tìm xem có bao nhiêu bóng đèn sáng sau n vòng. Vì vậy, nếu đầu vào là 3, thì kết quả sẽ là 1. Điều này là do -
- Lúc đầu, ba bóng đèn đều [tắt, tắt, tắt].
- Sau vòng đầu tiên, ba bóng đèn [bật, bật, bật].
- Sau vòng thứ hai, ba bóng đèn [bật, tắt, bật].
- Sau vòng thứ ba, ba bóng đèn [bật, tắt, tắt].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Bước này là thẳng tiến, chúng ta phải tìm căn bậc hai của n và trả về.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
main(){
Solution ob;
cout << (ob.bulbSwitch(3));
} Đầu vào
3
Đầu ra
1