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

|

1990 Discussions

|

  • alex_k5
     + 0 comments

    def utopianTree(n): h = 1 for i in range(n//2): h = h*2+1

    return h if n% 2==0 else h*2

  • nabendudas_mca22
     + 0 comments

    Here is a nice c# recurcive solution...

    public static int utopianTree(int n)
    {
        if(n == 0){
            return 1;
        }
        if(n==1){
            return 2;
        }
        if(n>1){
            if(n % 2 == 0){
                return utopianTree(n-1) + 1;
            }else{
                return utopianTree(n-1)*2;
            }
        }else{
            return 0;
        }
    }

  • goalhemanthu12
     + 0 comments

    JAVA

    public static int utopianTree(int n) {

    int h=0;

for(int i=0;i<=n;i++){

    if(i%2==0){

        h++;

    }else h*=2;
}
return h;
}

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

  • sergio777leviat1
     + 0 comments

    Python solution

    def utopianTree(n):
    cont = 0
    for i in range(n+1):

        if (i % 2) == 0:
            cont+=1
        else:
            cont*=2
    
    return cont