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

Sort by

recency

|

2012 Discussions

|

  • 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;
}

  • highsoft_soi
     + 0 comments

    Perl:

    sub utopianTree {
    my $n = shift;
    
    return ($n % 2 == 0) ? (2 ** (($n / 2) + 1)) - 1 : (2 ** ((($n + 1) / 2) + 1)) - 2;
}

  • yashu895150
     + 0 comments
    int height = 0;
    int i = 0;
    while(i<=n) {
        height = i % 2 ==0 ? height + 1 : height * 2;
        i++;
    }
    return height;

  • karim_dinani96
     + 0 comments
    if(n%2==0)
    height = pow(2,(n/2) +1) -1 ;
else
    height = pow(2,((n+1)/2) +1) -2 ;

  • borisvdb09
     + 0 comments

    C#

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

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in