problem statement:

Chef recently came to know about a theorem, which states that any natural number n can be uniquely represented as a sum of Fibonacci numbers:

N=Fk1+Fk2+…+Fkr

such that k1≥k2+2, k2≥k3+2, …,(i.e.: the representation cannot use two consecutive Fibonacci numbers).

It follows that any number can be uniquely encoded in the Fibonacci coding. And we can describe this representation with binary codes d0d1d2…ds1, where di is 1 if Fi+2 is used in the representation. The code will be appended by a 1 to indicate the end of the code word. Notice that this is the only occurrence where two consecutive 1-bits appear. Here are the a few examples:

1 = 1 = f2 =(11)

6 = 5+1 = f5 +f2 =(10011)

19 =13+5+1=f7+f5+f2 =(1001011)

Being a worthy friend of chef, this becomes your duty to encode the numbers and help chef.

solution:

#include<stdio.h>

#include<stdlib.h>

// To limit on the largest Fibonacci number to be used

#define N 30

/* Array to store fibonacci numbers. fib[i] is going

to store (i+2)'th Fibonacci number*/

int fib[N];

// Stores values in fib and returns index of the largest

// fibonacci number smaller than n.

int largestFiboLessOrEqual(int n)

{

fib[0] = 1; // Fib[0] stores 2nd Fibonacci No.

fib[1] = 2; // Fib[1] stores 3rd Fibonacci No.

```
// Keep Generating remaining numbers while previously
// generated number is smaller
int i;
for (i=2; fib[i-1]<=n; i++)
fib[i] = fib[i-1] + fib[i-2];
// Return index of the largest fibonacci number
// smaller than or equal to n. Note that the above
// loop stopped when fib[i-1] became larger.
return (i-2);
}
```

/* Returns pointer to the char string which corresponds to

code for n */
char* fibonacciEncoding(int n)

{

int index = largestFiboLessOrEqual(n);

```
//allocate memory for codeword
char *codeword = (char*)malloc(sizeof(char)*(index+3));
// index of the largest Fibonacci f <= n
int i = index;
while (n)
{
// Mark usage of Fibonacci f (1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used (0 bit),
// progress backwards
while (i>=0 && fib[i]>n)
{
codeword[i] = '0';
i = i - 1;
}
}
//additional '1' bit
codeword[index+1] = '1';
codeword[index+2] = '\0';
//return pointer to codeword
return codeword;
}
int main(void) {
int n;
scanf("%d",&n);
printf(fibonacciEncoding(n));
return 0;
}
```