Bật tắt đèn trong JavaScript

Mô tả vấn đề

Xét tình huống: Có n bóng đèn ban đầu tắt. Ta bật tất cả. Sau đó tắt mỗi đèn thứ 2. Lượt 3, chuyển trạng thái mỗi đèn thứ 3 (bật nếu tắt, tắt nếu bật).

Nói chung, lượt i, chuyển trạng thái mỗi đèn thứ i. Cuối cùng lượt n, chỉ chuyển đèn cuối. Viết hàm nhận n, trả về số đèn còn bật sau n lượt.

Ví dụ, nếu đầu vào là:

const n = 4;

Thì đầu ra nên là:

const output = 2;

Giải thích đầu ra

Trong mảng trạng thái, 0 = tắt, 1 = bật:

Sau lượt 5 chỉ còn 2 đèn bật.

Ví dụ minh họa

Mã thực hiện (nghiệm quan trọng: chỉ đèn số chính phương mới bật):

const n = 5; 
const findOn = (n = 1) => { 
  let off = 0; 
  let on = n; 
  while(off <= on){ 
    let mid = Math.floor((off + on) / 2); 
    if(mid * mid > n){ 
      on = mid - 1; 
    }else{ 
      off = mid + 1; 
    }; 
  }; 
  return Math.floor(on); 
}; 
console.log(findOn(n));

Đầu ra

Kết quả trong console sẽ là:

2