某实验逻辑电路中,初始时有 cnt
个观测点处于低电平状态。
对于某个观测点的电平调整意味着:如果观测点处于低电平,会被调整为高电平;而观测点处于高电平,会被调整为低电平。
第 1 轮,每个观测点调整一次电平。即,所有观测点处于高电平;
第 2 轮,每两个观测点调整一次电平。即,第 1、3、5 … 个观察点不调整,第 2、4、6 … 个观察点调整;
第 3 轮,每三个观测点调整一次电平。即,第 1、2、4、5 … 个观察点不调整,第 3、6 … 个观察点调整;
第 i
轮,每 i
观测点调整一次电平。 而第 cnt
轮,你只调整最后一个观测点的电平。
请找出 cnt
轮之后有多少处于高电平状态的观测点。
示例 1:
1 | 输入:cnt = 4 |
示例 2:
1 | 输入:cnt = 0 |
示例 3:
1 | 输入:cnt = 2 |
提示:
0 <= cnt <= 109
This is also a problem of “2015 百度 大数据开发工程师 的面试题”
电平能被调整的时候只有这个轮数n是改观测点的因子。
并且当因子不同的时候,两个因子就能抵消调整。
所以因子个数是复数的时候,就可以相当于没有进行操作,处于低电平。
所以就是找到因子个数是单数的的观测点。即1~n之间的因子个数是单数的数的数量。
因为任意一个数都能表示成a*b的形式,当a = b的时候,则只能调整一次,不能抵消。其余的因子都可以抵消。
所以就是找1~n中的完全平方数。
1 | class Solution { |