CareerCup

Before writing a program right away that counts the number of 0s and 1s printed, make a table with 3 columns:
1) "n"
2) "# of 0s printed"
3) "# of 1s printed"

Start filling in the first couple rows (i.e., for n=0, 1, 2, etc.):

n # of 0s printed # of 1s printed
0 1 0
1 0 1
2 1 1
3 1 2
4 2 3
5 3 5

Soon you'll realize that:
# of 0s printed = fib(n-1)
# of 1s printed = fib(n)

So the best solution is to just implement an efficient method for finding the (n-1)th and nth fibonacci numbers (e.g., iterative solution or recursive solution with memoization).

typedef std::pair<int, int> n10;

n10 numberOfOnesAndZeroes(int n)
{
	if (n == 0) return n10(0, 1);
	if (n == 1) return n10(1, 0);

	n10 _2 = n10(0, 1);
	n10 _1 = n10(1, 0);
	n10 res;

	int i;

	for (i = 1; i < n; ++i) {
		res.first = _1.first + _2.first;
		res.second = _1.second + _2.second;
		_2 = _1;
		_1 = res;
	}

	return res;
}

pair <int, int> Count0sAnd1s(int n)
{
int oldNum = 1;
int newNum = 1;
for (int i = 3; i <= n; i++)
{
int tmp = oldNum + newNum;
oldNum = newNum;
newNum = tmp;
}
return pair <int, int>(oldNum, newNum);
}

public class FibCounter{

private ArrayList<ArrayList<Integer>> counts;

public FibCounter(){
counts = new ArrayList<ArrayList<Integer>();
ArrayList<Integer> currCounts = new ArrayList<Integer>();
currCounts.add(1);
currCounts.add(0);
counts.add(currCounts);
currCounts.clear()
currCounts.add(1);
currCounts.add(0);
counts.add(currCounts);
}

public static void countZerosAndOnes(n){
int zeros = 0;
int ones = 1;
if (counts.size() < n){
zeros = counts.get(n-1).get(0) + counts.get(n-2).get(0);
ones = counts.get(n-1).get(1) + counts.get(n-2).get(1);
System.out.println("Zeros: " + zeros + " Ones: " + ones);
return;
}

zeros = countZerosAndOnes(n-2).get(0) + countZerosAndOnes(n-1).get(0);
ones = countZerosAndOnes(n-2).get(1) + countZerosAndOnes(n-1).get(1);

ArrayList<Integer> currCounts = new ArrayList<Integer>();
currCounts.add(zeros);
currCounts.add(ones);
counts.add(currCounts);

System.out.println("Zeros: " + zeros + " Ones: " + ones);
}
}

public class FiboCount {

    public static void main(String[] args) {
        Map<Integer, Output> cache = new HashMap<>();
        System.out.println(getFib(14, cache));

    }

    public static Output getFib(int n, Map<Integer, Output> cache) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        if (n == 0) {
            Output z = new Output(1, 0);
            cache.put(0, z);
            return z;
        }
        if (n == 1) {
            Output o = new Output(0, 1);
            cache.put(1, o);
            return o;
        }
        Output first = getFib(n - 1, cache);
        Output second = getFib(n - 2, cache);
        Output result = new Output(first.z + second.z, first.o + second.o);
        cache.put(n, result);
        return result;
    }

    private static class Output {

        int z;
        int o;

        public Output(int z, int o) {
            this.z = z;
            this.o = o;
        }

        @Override
        public int hashCode() {
            return o + z;
        }

        @Override
        public boolean equals(Object o) {
            if (this.getClass() != o.getClass()) {
                throw new IllegalArgumentException();
            }
            Output comp = (Output) o;
            return (this.z == comp.z && this.o == comp.o);
        }

        @Override
        public String toString() {
            return "Number of zeroes: " + z + '\t' + "Number of ones: " + o;
        }
    }

}

fib_Zero_And_One_Count(int n){

  int *zero =  new int[n+1];
  int *one =  new int[n+1];

  zero[0] = 1;
  zero[1] = 0;
  
  one[0] = 0;
  one[1] = 1;
  
  for(int i = 2; i<=n; ++i){
    zero[i] = zero[i-1] +zero[i-2];
    one[i] = one[i-1] + one[i-2];
  }
  
  printf("zero: %d, one: %d\n", zero[n], one[n]);

  delete [] zero;
  delete [] one;
}

package com.shashi.careercup;

public class FibonacciCount {

public static int op=0,op1=0;
public static void main(String args[])
{

System.out.println(fib(7));
System.out.print(op +" 0\'s and"+op1+" 1\'s"+" were printed ");
}
public static int fib(int n)
{

if(n==0)
{

op++;
return 0;
}
if(n==1)
{


op1++;
return 1;
}

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

#include<stdio.h>

int count0=0,count1=0;

int fib(int n){
if(n==0){
count0++;
return 0;
}
if(n==1){
count1++;
return 1;
}

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

int main(){
int ip,op;

printf("Enter the number:\t");
scanf("%d",&ip);

op=fib(ip);
printf("Output is %d",op);
printf("\nNumber of 0 is %d and Number of 1's are %d",count0,count1);
return 0;
}

#include <iostream>

using namespace std;

static int n0 = 0;
static int n1 = 0;

int fib(int n) {
if (n == 0) {
n0++;
return 0;
} else
if (n == 1) {
n1++;
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}

int main(int argc, const char * argv[]) {

std::cout << fib(14) << std::endl;

std::cout << "The number 0 is printed " << n0 << std::endl;

std::cout << "The number 1 is printed " << n1 << std::endl;

return 0;
}

It can be solved using static variable

int fib (int n) 
{
	static int cntOne,cntZero;
		
	if (n == 0)
	{
		cout<< "0";
		cntZero++;
		return 0;
	}

	if (n == 1)
	{
		cout << "1";
		cntOne++;
		return 1;
	}
	
	return fib(n-1) + fib(n-2);

}