ORIGIN

开关灯&调整电平

ACM 2 mins573 words

乐鑫02. 调整电平

某实验逻辑电路中,初始时有 cnt 个观测点处于低电平状态。

对于某个观测点的电平调整意味着:如果观测点处于低电平,会被调整为高电平;而观测点处于高电平,会被调整为低电平。

第 1 轮,每个观测点调整一次电平。即,所有观测点处于高电平;

第 2 轮,每两个观测点调整一次电平。即,第 1、3、5 … 个观察点不调整,第 2、4、6 … 个观察点调整;

第 3 轮,每三个观测点调整一次电平。即,第 1、2、4、5 … 个观察点不调整,第 3、6 … 个观察点调整;

i 轮,每 i 观测点调整一次电平。 而第 cnt 轮,你只调整最后一个观测点的电平。

请找出 cnt 轮之后有多少处于高电平状态的观测点。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:cnt = 4
输出:2
解释:
初始时, 电平状态为 [低, 低, 低,低],
第一轮后, 电平状态 [高, 高, 高, 高],
第二轮后, 电平状态 [高, 低, 高, 低],
第三轮后, 电平状态 [高, 低, 低, 低],
第四轮后, 电平状态 [高, 低, 低, 高],

最终有 2 个处于高电平状态的观测点,因此返回 2

示例 2:

1
2
输入:cnt = 0
输出:0

示例 3:

1
2
输入:cnt = 2
输出:1

提示:

  • 0 <= cnt <= 109

This is also a problem of “2015 百度 大数据开发工程师 的面试题”

Analysis

电平能被调整的时候只有这个轮数n是改观测点的因子。

并且当因子不同的时候,两个因子就能抵消调整。

所以因子个数是复数的时候,就可以相当于没有进行操作,处于低电平。

所以就是找到因子个数是单数的的观测点。即1~n之间的因子个数是单数的数的数量。

因为任意一个数都能表示成a*b的形式,当a = b的时候,则只能调整一次,不能抵消。其余的因子都可以抵消。

所以就是找1~n中的完全平方数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:

int adjustLevel(int cnt) {
int i = 1;
int ans = 0;
while(sqrt(cnt) >= i) {
ans ++;
i ++;
}
return ans;
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|