CareerCup

Count of 0 an 1 will grow proprtionally to Fibonachi sequence :
fib(3) 3
fib(4) 5
fib(5) 8
fib(6) 13 ans so on...

/**
 * How many times 0's and 1's will be printed in the following code:
 * int fib(int n) {
 *   if (n == 0) {print (0); return 0};
 *   if (n == 1) {print (1); return 1};
 *   return fib(n-1) + fib (n-2);
 *
 * }
 */
class FibPrint {
  public static void main(String[] args) { 
    int[] z1 = print(Integer.valueOf(args[0]));
    System.out.println("0 will be printed: " + z1[0] + " times");
    System.out.println("1 will be printed: " + z1[1] + " times");
  }
  static final int[] zero = new int[]{1, 0};
  static final int[] one = new int[]{0, 1};
  static int[] print(int n) {
    if (n == 0) 
      return zero;
    if (n == 1)
      return one;
    int[] f = print(n-1);
    int[] s = print(n-2);
    return new int[]{f[0]+s[0], f[1]+s[1]};
      
  } 
}

I don't think I get the point of this,

just declare a global printResult[0,0].
while 0 or 1 printed, printResult[0]+1 or printResult[1]+1.
You may choose to assert add into 2x if in fib().

Call fib then you get number you want print in array after execute.

Is this that simple? or any point deep inside that I missed?

Thanks for help guys

Here is proper implementation for the given question..

#include<stdio.h>

int fib(int n);
int count0,count1;

main()
{
    int n,T;


    scanf("%d",&T);

    while(T>0)
    {
        count0=0;
        count1=0;

        scanf("%d",&n);
        fib(n);
        printf("%d %d\n",count0,count1);
        T--;
    }
}

int fib(int n)
{


    if(n==0)
    {
        count0++;
       return 0;
    }

    if(n==1)
    {
          count1++;
          return 1;
      }


    return (fib(n-1)+fib(n-2));

}

Let's look at it in another way:
We know that fib(0) is called only within fib(2), while fib(1) is called within fib(2) and fib(3). Let call(k) be the times fib(k) is called, we actually have this:
call(0) = call(2)
call(1) = call(2) + call(3)
call(2) = call(3) + call(4)
...
call(n-2) = call(n-1) + call(n)
call(n-1) = call(n) = 1
Calculate from bottom up, we have:
call(n) = 1 = Fibonacci(1)
call(n-1) = 1 = Fibonacci(2)
call(n-2) = 1 + 1 = 2 = Fibonacci(1) + Fibonacci(2) = Fibonacci(3)
call(n-3) = 2 + 1 = 3 = Fibonacci(2) + Fibonacci(3) = Fibonacci(4)
...
call(2) = Fibonacci(n - 3) + Fibonacci(n - 2) = Fibonacci(n - 1)
call(1) = Fibonacci(n - 2) + Fibonacci(n - 1) = Fibonacci(n)
call(0) = call(2) = Fibonacci(n-1)
The above Finonacci(k) is the k-th fibonacci number.

you cant use naive recursive to solve it, that's too inefficient, and is absolutely not the interviewer want. actually, the formula is straightforward.
let <a,b> denotes 0 and 1 call times.
f(n=0) <a,b>=<1,0>
f(n=1) <a,b>=<0,1>
f(n=2)=f(n=1)+f(n=0)=<1,1>
f(n=3)=f(n=2)+f(n=1)=<1,2>
f(n=4)=f(n=3)+f(n=2)=<2,3>

we can solve it with O(n) complexity and O(1) space:

pair<int,int> count(int n)
{
        if(n<0) return make_pair(0,0);
	pair<int,int> a,b;
	a = make_pair(1,0);
	b = make_pair(0,1);
	if(n == 0) return a;
        if(n == 1) return b;
	pair<int,int> c;
	for(int i = 2; i <= n; ++i)
	{
		c.make_pair(a.first+b.first,a.second+b.second);
		a = b;
		b = c;
	}
	return c;
}

I think this question is related to performance of Iterative vs. Recursive fibonacci. The recursive operation becomes costly when the number becomes big because of the heavy call stack use.

Number N = 1's will be printed N-1 times and 0's will be printed N-2 times.
Number 4 = 1's - 3 times, 0's - 2 times
Number 10 = 1's - 9 times, 0's - 8 times

hope this helps.

WHAT IS A COMPUTER SCIENTIEST AT AKAMAI DOING, TRYING TO GET HER FUCKING HOMEWORK DONE!!??