319.灯泡开关.md

319.灯泡开关

/*
 * @lc app=leetcode.cn id=319 lang=typescript
 *
 * [319] 灯泡开关
 */

// @lc code=start
function bulbSwitch(n: number): number {}
// @lc code=end

解法 1: 模拟

function bulbSwitch(n: number): number {
  const bulbs = [...new Array(n)].map((_, i) => (i + 1) & 1)
  for (let i = 3; i < n; i++) {
    for (let j = 0; j < bulbs.length; j++) {
      if ((j + 1) % i === 0) bulbs[j] ^= 1
    }
  }
  let res = 0
  if (n > 2) bulbs[n - 1] ^= 1
  for (const bulb of bulbs) {
    if (bulb) res++
  }
  return res
}

解法 2: 数学

function bulbSwitch(n: number): number {
  if (n < 2) return n
  return Math.floor(Math.sqrt(n))
}

Case

test.each([
  { input: { n: 3 }, output: 1 },
  { input: { n: 0 }, output: 0 },
  { input: { n: 1 }, output: 1 },
  { input: { n: 2 }, output: 1 },
  { input: { n: 4 }, output: 2 },
  { input: { n: 10 }, output: 3 },
  { input: { n: 100 }, output: 10 },
  { input: { n: 1000 }, output: 31 },
  // { input: { n: 100000 }, output: 316 },
])('input: n = $input.n', ({ input: { n }, output }) => {
  expect(bulbSwitch(n)).toEqual(output)
})