# Utopian Tree Hackerrank problem solution

##### Utopian Tree Hackerrank

The Utopian Tree Hackerrank is a problem in which the utopian tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after N growth cycles? Input Format

The first line contains an integer, T, the number of test cases.
T subsequent lines each contain an integer, N, denoting the number of cycles for that test case.

Constraints
1<=T<=10
0<=N<=60

Output Format

For each test case, print the height of the Utopian Tree after N cycles. Each height must be printed on a new line.

Sample Input

3
0
1
4
Sample Output

1
2
7
Explanation

There are 3 test cases.

In the first case (N=0), the initial height (H=1) of the tree remains unchanged.

In the second case (N=1), the tree doubles in height and is 2 meters tall after the spring cycle.

In the third case (N=4), the tree doubles its height in spring (H=2), then grows a meter in summer (H=3), then doubles after the next spring (H=6), and grows another meter after summer (H=7). Thus, at the end of 4 cycles, its height is 7 meters.

##### Solution

Let us consider s is the height of the tree.

If the current season is summer one, height will increase by one unit, i.e. s++
Else, season will be monsoon and height will be twice, i.e. 2*s
The two seasons then alternate.
C

``````#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
int t,x=1,a;
scanf("%d",&t);
for(int a0 = 0; a0 < t; a0++){
int n;
scanf("%d",&n);
if(n==0)
a[a0]=x;
else if(n%2==0)
{
while(n!=0){
x=2*x+1;
n-=2;
}
}
else{
while(n!=1){
x=2*x+1;
n-=2;
}
if(n==1){
x=2*x;
}

}

a[a0]=x;
x=1;
}
for(int a0 = 0; a0 < t; a0++){
printf("%d\n",a[a0]);
}
return 0;
}

``````

C++

HOW TO THINK:

Since the sapling is planted during the onset of spring and the initial height of the sapling is 1m, hence the next cycle is summer. Thus, n initially during plantation is 1, so n when odd represents spring whereas when even represents summer. So when i is odd height is doubled but when even is increased by 1.

``````#include <bits/stdc++.h>

using namespace std;

// Complete the utopianTree function below.
int utopianTree(int n) {
int h=1;
for (int i=1;i<=n;i++)
{
if(i%2==0)
{
h=h+1;
}
else
{
h=h*2;
}
}
return h;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int t;
cin >> t;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

for (int t_itr = 0; t_itr < t; t_itr++) {
int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

int result = utopianTree(n);

fout << result << "\n";
}

fout.close();

return 0;
}``````

C++ II

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
int T, N, i;
cin >> T;
while(T--) {
cin >> N;
long long int s = 1;
for (i = 1; i <= N; i++) {
if(i % 2 == 0)
s++;
else
s = 2*s;
}
cout << s << endl;
}
return 0;
}```

C++ III

```#include <bits/stdc++.h>

using namespace std;

int fast_exp(int base, int exp) {
int res = 1;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base);
base = (base * base);
exp /= 2;
}
return res;
}

int main() {
int t;
int n, i;
cin >> t;
for (i = 0; i< t; i++) {
cin >> n;
cout << fast_exp(2, (n + 1) / 2 + 1) - 1 - (n % 2) << endl;
}
return 0;
}```

Java

``````import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;

public class Solution
{
public static void main(String[] args) throws NumberFormatException, IOException
{

PrintWriter printWriter = new PrintWriter(System.out);

while(testCount-- > 0)
{
}

printWriter.flush();
}

{
long h = 1;

for(int i = 1 ; i <= n ; i++)
{
if(i % 2 != 0)
h *= 2;
else
h +=1 ;
}

return h;
}
}
``````

Python

``````for _ in range(input()):
n=input()
print pow(2,(n+1)/2+1)-1-(n%2)``````

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi