转面试题：跑灯

2019独角兽企业重金招聘Python工程师标准原题有100盏灯依次编号1-100初始都是关着的。第1次遍历打开全部的灯依次编号1-100初始都是关着的。第1次遍历打开全部的灯第2次遍历关掉第2盏、第4盏等被2整除的灯第3次打开被3整除的灯第i次对被i整除的灯做如下操作 如果灯开着就关掉 如果灯关着就打开 如此交替进行直到100次遍历完毕请问还有多少盏灯亮着。

分析 这个题目比较好玩儿路子走对了很简单。想不对方法就不是那么美。

例如方向不对的话就按照题目的意思一遍又一遍的遍历直到结束时间复杂度是O(n^2)的。也能够解决问题但是复杂了。

那么怎么办呢上面的遍历的做法是横向的思路现在我们纵向思考。 一盏灯会在那几次被操作。例如编号为100的灯

第1次能够操作打开

第2次能够操作关闭

第4次能够操作打开

第5次能够操作关闭

第10次能够操作打开

第20次能偶操作关闭

第25次能够操作打开

第50次能够操作关闭

第100次能偶操作打开

最终编号为100的灯是打开的。再来看编号为70这盏灯

第1次能够操作打开

第2次能够操作关闭

第35次能够操作打开

第70次能够操作关闭

最终编号为70的灯关闭着。

通过上面两个例子我们会发现1,2,4,5等都是能够整除1001,2,35,70都能够整除70。 所以编号为n的灯有多少个因数就有会被操作多少次。很显然如果是偶数次则灯一定是关着的。 那什么情况下操作会是奇数次呢一个数每次分解都是两个数相乘只有当这两个数相同的时候才会是偶数次。 所以最终会亮着的灯都能够开平方得到一个正整数1,4,9,16,25,36,49,64,81,100.

【分析完毕】

转:https://my.oschina.net/dongdong2012/blog/162864