Блог пользователя maybesomeone

Автор maybesomeone, 2 года назад, По-английски

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;
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
#include<bits/stdc++.h>
using namespace std;

int main() {
  int n,ans = 0; cin >> n;
  n = abs(n);
  int f = 32 - __builtin_clz(n);
  while(f > 1) {
    f = (f+1) / 2;
    ans++;
  }
  cout << ans << endl;
}

This one works in O( log(log(n)) )

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    can you explain this ?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Instead of powerOfTwo(n) + 1 you can just write (31 — __builtin_clz(i)), result is the same I guess.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится
Just output the result of your function for the first few values of n.
Can't you notice a pattern?
Solution