is there any formula to calculate this in O(1)
?
int N;
cin >> N;
int answer = 0;
while (N > 1) {
N = sqrt(N);
answer++;
}
cout << answer;
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | atcoder_official | 148 |
5 | -is-this-fft- | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
10 | TheScrasse | 142 |
is there any formula to calculate this in O(1)
?
int N;
cin >> N;
int answer = 0;
while (N > 1) {
N = sqrt(N);
answer++;
}
cout << answer;
Название |
---|
This one works in O( log(log(n)) )
can you explain this ?
Imagine bit representation of n, let it be n = 16 (in bits 10000), sqrt of 16 is 4 (in bits 100), if n = 25 (11001 in bits) sqrt is 5 (in bits 101), size of bit representation after sqrt is always (bit representation size + 1)/2, we need to make size equal of 1 so number of operations is log(bit representation size of n) because after every sqrt it becomes half of initial size, it's little hard for me to explain, sorry.
Instead of powerOfTwo(n) + 1 you can just write (31 — __builtin_clz(i)), result is the same I guess.
Yeah it's absolutely right.
We can see that result for $$${2 ^ {2 ^ n}}$$$ is $$$n + 1$$$. Result for $$${2 ^ {2 ^ n}} \leqslant k \leqslant {2 ^ {2 ^ n + 1}}$$$ is $$$n + 1$$$. So the formula for $$$n$$$ is $$$\log(\log(n)) + 1$$$. In C++ such function as
__builtin_clz
has O(1) complexity.Code (code works properly for int type, for 64-bit integers use
63 - __builtin_clzll(x)
):