Fibonacci coding encodes an integer into binary number using Fibonacci Representation of the number. The idea is based on Zeckendorf’s Theorem which states that every positive integer can be written uniquely as a sum of distinct non-neighbouring Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..).
The Fibonacci code word for a particular integer is exactly the integer’s Zeckendorf representation with the order of its digits reversed and an additional “1” appended to the end. The extra 1 is appended to indicate end of code (Note that the code never contain two consecutive 1s as per Zeckendorf’s Theorem. The representation uses Fibonacci numbers starting from 1 (2’nd Fibonacci Number). So the Fibonacci Numbers used are 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, …….
Given a number n, print its Fibonacci code.
Input: n = 1 Output: 11 1 is first Fibonacci number in this representation and an extra 1 is appended at the end. Input: n = 11 Output: 001011 11 is sum of 8 and 3. The last 1 represents extra 1 that is always added. A 1 before it represents 8. The third 1 (from beginning) represents 3.
We strongly recommend you to minimize your browser and try this yourself first.
The following algorithm takes an integer as input and generates a string that stores Fibonacci Encoding.
Find the largest Fibonacci number f less than or equal to n. Say it is the i’th number in the Fibonacci series. The length of codeword for n will be i+3 characters (One for extra 1 appended at the end, One because i is an index, and one for ‘