Utopian Tree

Utopian Tree

  August 23, 2017    

---

Explanation:

Here as i Analysed that if n is divisible by 2 then it is equal to sum of last two occurrence  +1 
Else
Last occurrence +1

Time complexity : O(1) { if array is preprocessed}


Code:

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int arr[]=new int[61];
        arr[0]=1;
        arr[1]=2;
        for(int i=2;i<61;++i)
        {
            if(i%2==0)
            {
                arr[i]=arr[i-1]+1;
            }
            else
            {
                arr[i]=arr[i-1]+arr[i-2]+1;
                
            }
        }
        Scanner ab=new Scanner(System.in);
        int t=ab.nextInt();
        while(t-->0)
        {
            System.out.println(arr[ab.nextInt()]);
        }
    }
}