CareerCup

f(n) = f(n - 1) + f(n - 2)

Basically we need to build the string using either "1" or "10".
We can do this with simple for loope

int total = 0;
//i is no. of"10" in the string
for(int i=0;i<=K/2;i++){
        if(i%2!=0)
            continue;
        total += fact(k-i)/(fact(i)*fact(k-2i));
}

int isValid(char* str,int k)
{
        int i;
        if(k<=0) return 0;
        for(i=0;i<k;++i)
        {
                if(str[i]=='0' && (i==0 || str[i-1]=='0'))
                        return 0;
        }
        return 1;
} 
 
void print(char* str,int k)
{
        int i;
        for(i=0;i<k;++i)
                printf("%c",str[i]);
        printf("\n");
}
 
int count;
 
void countValidString(char* str,int depth,int k)
{
        if(depth<0)
        {
                if(isValid(str,k)) 
                {
                        ++count;
                        print(str,k);
                }
        }
        else
        {
                str[depth]='0';
                countValidString(str,depth-1,k);
 
                str[depth]='1';
                countValidString(str,depth-1,k);
        }
}

Complete working code: ideone.com/cDPgI

This is actually a fibonacci sequence
So,
f(n)= ((1.618034)^n - (.618034)) / sqrt(5)

O(1) complexity, space and time

http://www.mathsisfun.com/numbers/fibonacci-sequence.html

public class generateRestrictedBinaryString {
	public static void main(String[] s) {
		int K = 5;
		System.out.println(numberOfPossibleBinaryStrings(K, 0));
	}
	static int numberOfPossibleBinaryStrings(int k, int last_digit) {
		if (k == 1) {
			if (last_digit != 0) {
				return 2;
			} else {
				return 1;
			}
		} else {
			if (last_digit != 0) {
				return numberOfPossibleBinaryStrings(k - 1, 0)
						+ numberOfPossibleBinaryStrings(k - 1, 1);
			} else
				return numberOfPossibleBinaryStrings(k - 1, 1);
		}
	}
}

Simple recursion solution for appending '1' or '0' to bit where counter == 0 -> 1 and last array endswith '0' -> 1

static void Main(string[] args)
        {
            char[] c = new char[5];
            PrintBinaryStrings(c.Length, 0, c);
        }

        private static void PrintBinaryStrings(int k, int counter, char[] c)
        {
            if (counter == k)
            {
                Console.WriteLine(new string(c));
                return;
            }
            else if (counter < k)
            {

                // Concat 1
                c[counter] = '1';
                PrintBinaryStrings(k, counter + 1, c);

                // Concat 0
                if (counter > 0 && c[counter - 1] != '0')
                {
                    c[counter] = '0';
                    PrintBinaryStrings(k, counter + 1, c);
                }
            }
        }

Let us have two arrays arr_zero and arr_one of length K.
Now arr_zero[0] = 0, arr_one[0] = 1 ( i.e. 1)
arr_zero[1] = arr_one[0] = 1, arr_one[1] = arr_zero[0]+arr_one[0] = 1 (i.e. 10, 11)
arr_zero[2] = arr_one[1], arr_one[2] = arr_zero[1] + arr_one[1] (i.e. 110, 101, 111)
and so on...
valid string count for length K = arr_zero[K-1] + arr_one[K-1]

Code :

#include <stdio.h>


int  main()
{
	int K;
	unsigned int count = 0;
	
	scanf("%d", &K);

	if(K > 0)
	{
		unsigned int i = 1;
		unsigned int zero_count = 0, one_count = 1;
	
		while(i < K)
		{
			unsigned int temp = zero_count;
			zero_count = one_count;
			one_count += temp;
			i++;
		}

		count = zero_count+one_count;

	}
	
	printf("%u", count);

	return 0;
}

can any probability be used here ..? since they have asked just for a count

It seems to me that the question is more about performance. Are you going through k bits of each of 2^k strings? Since MSB cannot be 0, 2^(k-1) strings.

public static int question(int size)
{
 if(size==0)
    return 1;
 else if(size<0)
    return 0;
 else
  {
      int startWith1=question(size-1);
      int startWith10=question(size-2);
      return startWith1+startWith10;
  }
}

int c=0;
 int s(int i,int k);
main()
{
      s(1,3);
      printf("%d",c);
      getch();
      }
      int s(int i,int k)
      {
          if(k==1)
          {c++;return 0;}
          if(k<=0)
          return 0;
          if(i==0)
          s(1,k-1);
          if(i==1)
          {s(0,k-1);
          s(1,k-1);
          }
      }

C++ Solution :

#include<iostream>
#include<cstring>

using namespace std;

int count=0;

void cnt(char str[],int k,int i)
{

	// last character....
	if(i==k)
	{
		count++;
		return;
	}
	
	// i is length....
	int j;
	char str1[i+1];
	for(j=0;j<i;j++)
		str1[j] = str[j];
		
	if(str[j-1]=='0')
	{
		str1[j] = '1';
		str1[j+1] = '\0';
		cnt(str1,k,i+1);
	}
	else
	{
		str1[j] = '1';
		str1[j+1] = '\0';
		cnt(str1,k,i+1);
		str1[j] = '0';
		str1[j+1] = '\0';
		cnt(str1,k,i+1);
	}
	
	return;
}

int main()
{
	int k;
	cout << "Enter K = ";
	cin >> k;

	char str[] = {'1','\0'};

	cnt(str,k,1);
	
	cout << "\nNumber of strings : " << count << endl;

	return 0;
}

I started thinking about how to generate such a string. If I start with string with all 1s: 1111
then the first value I can vary is position 3 (going left to right). If I leave it as 1 next value is 2, other wise if I change it next position is 1.

The relation is m(4) = m(3) + m(2) (as was pointed out already)

This is also fibonacci, which is a no-no. Instead I will build my solution up one value at a time:

private static int countPossibleStrings(int length) {
    int[] solution = new int[length];
    solution[0] = 1; // Length = 1
    solution[1] = 2; // Length = 2

    for (int i = 2; i < solution.length; i++) {
      solution[i] = solution[i - 1] + solution[i - 2];
    }
    return solution[solution.length - 1];
  }

#include<iostream>
#include<string>
using namespace std;
int cal(int i,int k,string s)
{
if(i==k)
{
cout<<s<<endl;
return 1;
}
if(i==0||s[i-1]=='1')
{
if(i==0)
return cal(i+1,k,s+'1');
else
return cal(i+1,k,s+'0')+cal(i+1,k,s+'1');
}
else
{
return cal(i+1,k,s+'1');
}
}
int main()
{
string s;
int k;
cin>>k;
cout<<cal(0,k,s);
}

int possibleCombination( const std::string& inputStr )
{
int numZeros = 0;
for( int i = 0; i< inputStr.size(); i++ )
if( '0' == inputStr[i] )
numZeros++;

int numOnes = inputStr.size() - numZeros;
if( numZeros > numOnes )
return 0;
int numOneZeroPair = numZeros; //only '10' pairs
int numBalOnes = numOnes - numZeros; //only 1's

//now the problem is permute '10' and '1'
return (fact(numOneZeroPair + numBalOnes) /(fact(numOneZeroPair) * fact(numBalOnes) )
}

no need to write any algorithm its just 2^(k/2)

as there at most k/2 0s in which we have to find combination of 0s or 1s
k/2 must be 1s as each 0 must have 1 in his left

so it takes O(1) time

Javascript solution - dynamic programing
var k = 7 //
var array = [1, 0]
var finalsum = 1
for (var i = 0; i < k; ++i) {
var tmp = array[1]
array[1] = array[1] + array[0]
array[0] = tmp
console.log(array[0]+ " "+array[1]);
finalsum = array[0] + array[1]
}

console.log(finalsum);

#include<stdio.h>
int main()
{
        int k,i;
        unsigned long long int ans;
        scanf("%d",&k);
        unsigned long long int arr[k+1];
        arr[1]=1;
        arr[2]=2;
        for(i=3;i<=k;i++)
        {
                arr[i]=arr[i-1]+arr[i-2];
        }
        printf("%llu",arr[k]);
}