CareerCup

Summation of (3^(i/2) * 4^(i-1)/2) ,where i runs from 1 to k.

Here i/2 and (i-1)/2 are the integral values of quotients.

O(1) solution

	number of children at even level = 4
	number of children at odd level  = 3
	
	x = 1 + 4;
	y = 4 * 3;

	int n = (level-1)/2 - 1;
	double res;

	if(level % 2)
		res = (pow(y, n+1)*(x+y-1)-x) / (y-1);
	else
		res = x + (x*y*(pow(y, n+1)-1)) / (y-1);

	cout << res << endl;


below is proof

number of nodes	      level
1			               1
4			               2
4*3		   	               3
4*3*4			      4
4*3*4*3			      5
4*3*4*3*4		      6
4*3*4*3*4*3		      7
4*3*4*3*4*3*4	      8

lets take odd level at 7
1 + 4 + 4*3 + 4*3*4 + 4*3*4*3 + 4*3*4*3*4 + 4*3*4*3*4*3
1 + 4 + 4*3 ( 1 + 4 + 4*3 + 4*3*4 + (4*3)^2)
1 + 4 + 4*3 ( 1 + 4 + 4*3 (1 + 4 + (4*3))

lets take x = 1+4 and y = 4*3

this equation looks like 

x + y (x + y (x + y))
x + y (x + xy + y^2)
x + xy + xy^2 + y^3
x (1 + y + y^2) + y^3
...
this is summation series x ( 1+ y + y^2 + y^3+ y^4....+y^n) + y^(n+1) 

summation for 1+ y + y^2 + y^3+ y^4....+y^n = (y^(n+1) - 1) / (y-1)

answer for odd levels is  x(y^(n+1)-1)/(y-1) + y^(n+1)

for even level it will be

x + xy + xy^2 + xy^3 + xy^4...
x + xy(1 + y + y^2 + y^3 + ...)

after solving the summation series for even levels is

x + xy(y^(n+1)-1)/(y-1)

simple DP problem

Let n[1...k] be the array of node_count at level i where 1 < = i <= k. We need not go beyond k as all the leaves are at level k

So,the desired result is n[1] +....+n[k]

The recurrence relation in the DP is

n[i+1] = 3 * n[i] if i %2==1,
       = 4 * n[i] , otherwise

Code :
   n[1] = 1 //  this represents the root node 
   numNodes = n[1];
   for( i = 2 : i <= k ; i++){
          if((i-1) %2 ==1){
                      n[i] = 3 * n[i-1];
		}
           else {
                       n[i] = 4 * c=n[i-1];
                }
            numNodes += n[i];
	}
      print(numNodes);

It's simple mathematics , You can solve it in O(1):

int number_of_nodes(int k ){
	int result = 0;
	if (k % 2 == 0){
		result = (Math.pow(12 , k/2 - 1) - 1) / 11  + 3 * ( Math.pow(12, (k-1)/2) -1) /11 ;
	}else{
		result = (Math.pow(12,(k-1)/2) - 1) / 11 + 3 * (Math.pow(12,(k-1)/2 - 1 ) - 1 )/ 11;
	}
}

This is geometric progression problem. Can resolve it by doing odd and even levels separately and sum them. Someone may be able to improve this.

In summary, the geometric progression for odd levels is
a=(4.3.4.3) = 144
r=4.3 = 12
Valid for k>=5.
The normal equation for geometric progression is
a*(1-r^m)/(1-r) where m is the number of terms in the series. Since 1st term is at k=5, 2nd term is at k=7, etc, we can get the Nth term using k/2-1.
a*[1-r^(k/2-1)]/(1-r)

Similarly, solving for even levels
a=3
r=(4.3)=12
Valid for k>=2
a*[1-r^(k/2)]/(1-r)

The Java code is given below.

public class SumNodes
{
    public static void sumNodes(int k) {
        int total = 0;
        if(k%2==0) { // even
            total = sumEvenLevel(k);
            total += sumOddLevel(k-1);
        }
        else {
            total = sumOddLevel(k);
            total += sumEvenLevel(k-1);
        }
        System.out.println("Total Nodes in tree with level " + k + ": " + total);
    }

    public static int sumEvenLevel(int k) {
        int retval = 0;
        int a = 3;
        if(k>=2) {
            retval = a * (1 - (int)Math.pow(12,k/2))/(-11);
        }

        return retval;
    }
    
    public static int sumOddLevel(int k) {
        if(k==1) return 1;
        if(k==3) return 13;
        int retval = 13;
        int a = 144;
        if(k>=5) {
            retval += a * (1-(int)Math.pow(12,k/2-1))/(-11);
        }
        return retval;
    }
    
    public static void main(String[] args) {
        sumNodes(Integer.parseInt(args[0]));
    }
}

There should be a mistake in the phrasing of this problem. A full tree by definition is a binary tree whose nodes have (strictly) either two (i.e., non-leaves) children or none(i.e., leaf-nodes).