We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Utopian Tree
  5. Discussions

Utopian Tree

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/0G-kEeQC25E

    Solution 1 : O(N)

    int utopianTree(int n) {
    int ans = 1;
    for(int i = 1; i <= n; i++){
        if(i % 2 == 0) ans++;
        else ans *=2;
    }
    return ans;
}

    Solutoin 2 : O(1)

    int utopianTree(int n) {
    string s(n / 2 + 1, '1');
    if(n % 2 == 1) s += '0';
    bitset<60> ans(s); 
    return ans.to_ullong();
}

    Solutoin 3 : O(1)

    int utopianTree(int n) {
    int ans = (1 << ((n / 2) + 1) ) - 1;
    if(n % 2 == 1) ans*=2;
    return ans;
}

    Solutoin 4 : O(1)

    int utopianTree(int n) {
    return ((1 << ((n / 2) + 1) ) - 1) << n%2;
}