319. Bulb Switcher

不念不忘少年蓝@ 2022-07-28 09:44 143阅读 0赞

问题描述：

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 
    
    At first, the three bulbs are [off, off, off].
    After first round, the three bulbs are [on, on, on].
    After second round, the three bulbs are [on, off, on].
    After third round, the three bulbs are [on, off, off]. 
    
    So you should return 1, because there is only one bulb is on.

有n盏电灯，序号设为1,2,3,...,n，初始状态都是关闭。现在对它们进行n次操作，第i次操作的对象是序号为i,2i,3i,...的电灯，每次操作改变其状态（关闭变成打开，打开变成关闭）。求最终有多少盏电灯打开。

解法：

如果使用两层循环，提交结果是Time Limit exceeded。考虑到该问题实际上是求对于每个i(1≤i≤n)，i能被多少个数整除，记为x（比如i=8，则1,2,4,8符合，8能被4个数整除），若x为偶数，该盏灯还是关闭的；反之亦然。现在再来看，一个数i，若有一个因子，必然能找到另一个因子为 i除以第一个因子的结果。只有某数是某数的平方，才为奇数。所以问题简单地归结为求sqrt(n)。

public class Solution {
        public static int bulbSwitch(int n) {
            double res = Math.sqrt(n);
            return (int)res;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 Bulb Switcher IV（C++灯泡开关 IV）

class Solution { public: int minFlips(string target) { char

柔情只为你懂/ 2023年01月02日 12:25/ 0 赞/ 130 阅读

相关 leetcode 319. Bulb Switcher | 319. 灯泡开关

题目 [https://leetcode.com/problems/bulb-switcher/][https_leetcode.com_problems_bulb-sw

àì夳堔傛蜴生んèń/ 2022年10月19日 13:58/ 0 赞/ 150 阅读

相关【codeforces】Bulbs

![这里写图片描述][20160721230838563] ![这里写图片描述][20160721230850345] ![这里写图片描述][2016072123090

淡淡的烟草味﹌/ 2022年09月24日 00:26/ 0 赞/ 129 阅读

相关 LeetCode319——Bulb Switcher

LeetCode319Bulb Switcher 原题题意我的思路标准答案 LeetCode3

川长思鸟来/ 2022年08月18日 12:30/ 0 赞/ 118 阅读

相关 319. Bulb Switcher

问题描述： There are n bulbs that are initially off. You first turn on all the bulbs. Then,

不念不忘少年蓝@/ 2022年07月28日 09:44/ 0 赞/ 144 阅读

相关 leetcode【67】-Bulb Switcher

题目描述： There are n bulbs that are initially off. You first turn on all the bulbs. Then

向右看齐/ 2022年07月21日 00:13/ 0 赞/ 3 阅读

相关 leetcode 319. Bulb Switcher 轮流开关灯泡 + 数学公式

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you tur

缺乏、安全感/ 2022年06月07日 01:08/ 0 赞/ 165 阅读

相关 leetcode 672. Bulb Switcher II 轮流开关灯泡 + 数学公式

There is a room with n lights which are turned on initially and 4 buttons on the wall. A

旧城等待，/ 2022年06月03日 07:37/ 0 赞/ 173 阅读

相关 leetcode【67】-Bulb Switcher

题目描述： There are n bulbs that are initially off. You first turn on all the bulbs. Then

╰+攻爆jí腚メ/ 2022年04月11日 05:57/ 0 赞/ 144 阅读

相关 LeetCode 319. Bulb Switcher

Description There are n bulbs that are initially off. You first turn on all the bulbs

梦里梦外;/ 2022年03月07日 14:14/ 0 赞/ 184 阅读