CareerCup

It's not hard to see that C(n) has the following recursive definition (similar to the Fibonacci numbers):
C(0)=1
C(1)=1
C(2)=2
C(n)=C(n-3)+C(n-2)+C(n-1) (if n>2)

This recursive definition leads to an obvious (and slow) algorithm for computing C(n). Slightly better is:

def C(n):
   L=[1,1,2]
   while n:
       n-=1
       new=L[0]+L[1]+L[2]
       L[0]=L[1]
       L[1]=L[2]
       L[2]=new
   return L[0]

This is okay, but still slow if n is very large. Faster algorithms can be found using linear algebra, similar to fast algorithms for the Fibonacci numbers. One way to regard the previous algorithm is to think of L=[1,1,2] as a vector, and then each iteration replaces L by M*L, where M is the matrix

[0 1 0]
[0 0 1]
[1 1 1]

So what we are really doing is computing the first entry of (M^n)*L. Fast algorithms for matrix exponentiation can accelerate this much faster than just repeatedly multiplying (on the left) by M, n times in a row.

Here is a different O(log n) algorithm (i.e different from the matrix method).

I will not explain this algorithm for now, will let you guys try and figure it out. But I will explain it later (after a few days), if no one posts an explanation and someone is actually interested in knowing.

Below is some python code and its output. I am just starting to learn python, so if you have some suggestions to write differently/better, I will be glad to know

Sorry if the post gets too long.

import time # for timing test.
import math # for pow
   
# tribonacci numbers satisfy t_{n+2} = t_{n-1} + t_{n} + t_{n+1}
# we start with t_{0} = 1, t_{1} = t_{2} = 2, t_{4} = 7.
# so first few are 1, 1,2,4,7,13,24,44,81,149,274.
# check out: // oeis.org / A000073
    
# Computes tribonacci numbers in O(log n) time.
def tribonacci(n):
	t = tribonacci_log(n)
	return t[2]
   
# returns the list [t_{n+2}, t_{n+1}, t_n]
def tribonacci_log(n):
	base_case = [274,149,81,44,24,13,7,4,2,1,1]
   
	# we have this as we compute upto t_{n/2 - 4}.
	if n <= 8:
		return base_case[8-n: 11-n]
    
	t = tribonacci_log(n/2)
    
	# compute t_{n-4}, t_{n-3},t_{n-2}, t_{n-1}
	for i in (1,2,3,4):
		x = t[-3] - (t[-1]  + t[-2])
		t.append(x)
    
	# t now looks like [t_{n+2}, ..., t_{n-4}]
	# t_{n} = t[2]	
    
	rett = [];
     
	# The crux of the algorithm.
	for i in (5,4,3):
		x = t[2]*t[i] + t[1]*(t[i] + t[i+1]) + t[0]*t[i-1]
		rett.insert(0,x)
    
	rett.insert(0,sum(rett));
    
	if n%2 == 0:
		return rett[-3:]
	else:
		return rett[-4:-1]
    
# Computes tribonacci numbers using the simple linear algo.
def tribonacci_linear(n):
	t = [1,1,2]
	while n > 0:
		t_new = t[0] + t[1] + t[2]
		t[0], t[1], t[2] = t[1], t[2], t_new
		n = n-1
	return t[0]
      
def tribonacci_correctness_test(num_values):
	if num_values <= 0 :
		return;
	print "Correctness Test (", num_values, ") :"
	passed = True
	for n in range(1, num_values, 1):
		if tribonacci(n) != tribonacci_linear(n):
			print "\t Failed", n, tribonacci(n)
			passed = False
	if passed:
		print "\t Passed"
      
def tribonacci_time_test(timing_value):
	print "Timing Test (", timing_value, ") :"
	delta1, t1 = time_func(timing_value, tribonacci);
	delta2, t2 = time_func(timing_value, tribonacci_linear);
	print "\tRecursive method:", delta1;
	print "\tLinear method:", delta2;
	print "\tComparing values:", t1 == t2
   
# yeah, can make it take multiple args, whatever.
def time_func(n, func):
	before = time.time()
	ret = func(n);
	after = time.time();
	return after - before, ret;
    	
    
def main():
	max_num_values = 2500
	tribonacci_correctness_test(max_num_values)
	max_timing_value = math.pow(10, 6)
	n = 1;
	while n <= max_timing_value:
		tribonacci_time_test(n)
		n = n*10
      
if __name__ == "__main__":
	main()

And this is the output

Correctness Test ( 2500 ) :
	 Passed
Timing Test ( 1 ) :
	Recursive method: 2.14576721191e-06
	Linear method: 9.53674316406e-07
	Comparing values: True
Timing Test ( 10 ) :
	Recursive method: 5.96046447754e-06
	Linear method: 3.09944152832e-06
	Comparing values: True
Timing Test ( 100 ) :
	Recursive method: 1.59740447998e-05
	Linear method: 3.40938568115e-05
	Comparing values: True
Timing Test ( 1000 ) :
	Recursive method: 3.2901763916e-05
	Linear method: 0.000290155410767
	Comparing values: True
Timing Test ( 10000 ) :
	Recursive method: 0.000332832336426
	Linear method: 0.00647592544556
	Comparing values: True
Timing Test ( 100000 ) :
	Recursive method: 0.0115561485291
	Linear method: 0.333210945129
	Comparing values: True
Timing Test ( 1000000 ) :
	Recursive method: 0.437210083008
	Linear method: 29.7244770527
	Comparing values: True

This problem is similar to coin change problem .. you can solve it using DP
value is the array containing all the possible values

C(n,i) = C(n,i+1)+c(n-value[i],i+1) // Recursive solution

Print out the selections:

void Choice(int& choice, int count, int cur, int arr[], int& pos)
{
if (count == cur)
{
int sum = 0;
for (int i = 0; i< count && sum < count; ++i)
{
printf("%d,", arr[i]);
sum += arr[i];
}
printf("\n\n");
++choice;
return;
}
else if (count < cur)
{
return;
}
else
{
for (int i = 1; i < count; ++i)
{
arr[pos] = i;
Choice (choice, count, i + cur, arr, ++pos);
--pos;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int pickNum = 4;
int arr[pickNum];
int choice = 0;
int pos = 0;
Choice(choice, pickNum, 0, arr, pos);

printf("C(N) = %d\n", choice);
return 0;
}

public static int countC(int n) {
		int ways = 0;
		if(n>2) {
			ways += countC(n-3);
			ways += countC(n-2);
			ways += countC(n-1);
		} else
		if(n>1) {
			ways += countC(n-2);
			ways += countC(n-1);
		} else {
			ways += 1;
		}
			
		return ways;
	}

Here is a solution without recursion or DP.
Define the combinations by the number of 1s, 2s and 3s in the sequence,
eg 112 has n3 =0, n2 = 1 and n1 =2
and 1111 has n3 = n2 = 0 and n1 =4

This way we can define different combinations by n1,n2,n3,
eg for n1=2,n2=1,n3=0 the three possible combinations are:
112
121
211
the total combinations = (n1+n2+n3)! / (n1! * n2! * n3! )


The maximum possible n3 for a number n is n/n3.
So all we have to do is loop over all the possible n1,n2,n3 for the given n and add the totals along the way.

The code is:

int C(int n){
int total = 0;
for(n3 = 0; n3<= n/n3; n3++){
 for(n2 = 0; n2 = (n - 3*n3)/2;n2++){
   n1 = n - 3*n3 - 2*n2
   total += fact(n1+n2+n3)/fact(n1)*fact(n2)fact(n3)
   }
  } 
return total;
}

Criticisms and comments welcome.

public int CnFunc(int n){
if(n==0) return 1;
int ways = 0;
for(int i=3;i>0;i--){
if(i<=n){
ways += CnFunc(n-i);
}
}
return ways;
}

"It's not hard to see that C(n) has the following recursive definition (similar to the Fibonacci numbers)"

Well, maybe I'm not smart enough. I'm not be able to figure out why C(n)=C(n-1)+C(n-2)+C(n-3)

for me
C(1)=1
C(2)=2
C(3)=4
C(4)=7
C(5)=10

And 7 + 4 + 2 = 13, not 10

why C(5)=10?
11111
2111
1211
1121
1112
311
131
113
32
23

Did I missed anything?

This code print all the permutations, it can be easily changed to print the total number. Also this algorithm prints n too.

#include <iostream>
#include <sstream>

void permutation(const int n,std::string preFix = "")
{
	if (preFix.empty()) {//first time only. can be taken out of this function
		for (int i = 0 ; i < n ; ++i)
			std::cout << preFix << 1;
			std::cout << std::endl;
	}
	for(int i=2; i<=n;i++) {
		int pos=0;
		while(pos <= (n - i)) {
			int numOfOnesAfterPos=0;
			std::ostringstream num;
			std::ostringstream newPreFix;
			bool addedPos=false;
			for(int j =0 ; j<n;++j) {
				if(j == pos) {
					num << i; 
					j+=i;
					addedPos=true;
					newPreFix << preFix << num.str();
				}
				if(j<n) {
					num << "1";
				    if (addedPos) {++numOfOnesAfterPos;}
                }	
			}
			std::cout << preFix << num.str() << std::endl;			
			permutation(numOfOnesAfterPos, newPreFix.str());
			++pos;
		}
	}  
}

int main ()
{
    std::cout << "start" <<std::endl;
    permutation(7);
    return 0;
}

#include<stdio.h>
#include<stdlib.h>

void print(int arr[],int n)
{
int j;
if(n!=1)
{for(j=0;j<n;j++)
printf("%d ",arr[j]);

printf("\n");
}
}

void comb(int n ,int index)
{
static int arr[100];
if(n==0)
{
print(arr,index);
return ;
}
else if(n>0)
{
int i;
for(i=1;i<=n;i++)
{
arr[index]=i;
comb(n-i,index+1);
}
}
}



main()
{
comb(4,0);
}

#include<stdio.h>
#include<stdlib.h>

void print(int arr[],int n)
{
int j;
if(n!=1)
{for(j=0;j<n;j++)
printf("%d ",arr[j]);

printf("\n");
}
}

void comb(int n ,int index)
{
static int arr[100];
if(n==0)
{
print(arr,index);
return ;
}
else if(n>0)
{
int i;
for(i=1;i<=n;i++)
{
arr[index]=i;
comb(n-i,index+1);
}
}
}



main()
{
comb(4,0);
}

public static int find(int n){
if(n < 0){
return 0;
}
if(n == 0){
return 1;
}
return find(n - 1) + find(n - 2) + find(n - 3);
}

int count(int n)
{
    if (n == 0) return 1;
    else if (n == 1) return 1;
    else if (n == 2) return 2;
    else return count(n-3) + count(n-2) + count(n-1);
}

This can be viewed as a BFS traversal of a graph.

public static int CalculateCn(int num){
    int count = 0; 
    ArrayList<Integer> queue = new ArrayList<Integer>(); 
    queue.add(0); 
    while(!queue.isEmpty()){
        int sum = queue.remove(0); 
        if(sum == num)
            count ++; 
        else
            for(int i=1;i<=Math.min(3, num-sum);i++)
                queue.add(sum+i); 
    }
    return count; 
}

Just found it even simpler with DFS (though the complexity is not good)

public static int CalculateCn(int sum, int num){
    if(sum > num)
        return 0; 
    if(sum == num)
        return 1; 
    if(sum < num)
        return CalculateCn(sum+1, num) + CalculateCn(sum+2, num) + CalculateCn(sum+3, num); 
}

int calc(int n) {

if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;

int c1 = 1;    
int c2 = 1;
int c3 = 1;

for ( int i = n ; i > 4 ; i-- ) {
  int temp = c2;
  c2 = c1 + c3;    
  c1 = c3;
  c3 += temp;
}

return 1*c1 + 2*c2 + 4*c3;
}

We can do this combinatorially. Since the items are all the same, we can imagine setting all the items side by side next to one another. Suppose we have 4 items, then our layout would look like:

O O O O

What we essentially want to do now is to see all possible ways we could group these items together, suppose we use a sticks to divide.

We can use 1 stick
O | O O O (1 + 3)
O O | O O (2 + 2)
O O O | O (3 + 1)

We can use 2 sticks
O | O | O O (1 + 1 + 2)
O | O O | O (1 + 2 + 1)
O O | O | O (2 + 1 + 1)

We can use 3 sticks
O | O | O | O (1 + 1 + 1 + 1)

Overall we can use anywhere from 1 to n-1 sticks. We get the closed form
C(n) = sigma (n-1) choose i where i = 1:n-1

import math

def C(n):
  totalWays = 0
  for x in range(1, n):
    totalWays += nCk(n-1,x)
  return totalWays

def nCk(n, k):
  if k == 0 or n == k:
    return 1

  return int(math.factorial(n) / (math.factorial(n-k) * math.factorial(k)))

public class Program15072768 {

	
	
	static int count = 0;
	
	
	static void C(int n,int tsum)
	{
		if(tsum == n)
		{
			count++;
			return;
		}
		else if(tsum > n)
		{
			return;
		}
		else{
			
			for(int i=1;i<n;i++)
			{
				
				C(n,i+tsum);
			}
		}
	}
	public static void main(String[] args) {
		 C(4,0);
		 System.out.println(count);
	}

}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("enter the number of identical items greater than 0");
string s = Console.ReadLine();
int x = int.Parse(s);
int firstgroup = 1;

abc ob = new abc();

Console.WriteLine(1+ob.NumberOfways(x));




Console.WriteLine();
}
}
class abc
{
public long NumberOfways(int n)
{
long prevalue=0;
for (int c = 1; c <= 3; c++)
prevalue=prevalue+ fact(n - c) / fact(n - c - 1);
return prevalue;




}
public long fact(int number)
{
if (number == 0)
return 1;
else
return number * fact(number - 1);
}
}

}

pattern should be:
C(1) = 0
C(2) = 1
C(3) = 3
C(4) = 7
C(5) = 15

which follows a trend of powers of 2. So it is just 2^(n-1) - 1

Solution is:

int C(int n)
{
return pow(2,n-1) - 1;
}

Why is C(4) = 7
I mean why are we not taking 1112, 1121, 1211,2111, 2211,1122??

import java.util.*;
public class Main {
	
	
	public static void main(String args[]){
		int num =4;
		int runningsum=0;
		ArrayList<Integer> perm = new ArrayList<Integer>();
		permutate(num,runningsum, perm);
	}
	
	public static void permutate(int num,int runningsum, ArrayList<Integer> perm){
		
		if(runningsum ==num){
			for(int i=0;i<perm.size();i++){
				System.out.print(perm.get(i) + " ");
			}
			System.out.println();
		}
		for(int i=1;i<=3 && i+runningsum<=num;i++){
			Integer cur = i;
			perm.add(cur);
			permutate(num,i+runningsum,perm);
			perm.remove(cur);
		}
	}
}