Finding the Zeckendorf Representation of a Positive Integer (BIO 2023 Q1)

Question

I was practicing question 1a of the British Informatics Olympiad 2023 past paper.

In the Fibonacci sequence each number is generated by adding the previous two numbers in the sequence. We will start with the numbers 1 and 2, so the sequence is 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … The Zeckendorf representation of the number n consists of the distinct numbers from the Fibonacci sequence which sum to n, where no two adjacent numbers from the Fibonacci sequence are used. There is always a unique representation.
For example:

• 21 is represented by the single number 21;
• 21 is not represented by 8 13, even though they sum to 21, as those numbers are adjacent in the Fibonacci sequence;
• 100 is represented by 3 8 89

The Zeckendorf representation for n always includes the largest number from the Fibonacci sequence that is no greater than n.

Write a program that reads in a number (between 1 and 1,000,000 inclusive) and outputs the numbers (in any order) in the corresponding Zeckendorf representation.

I wrote this code:

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


struct Node {
    int data;
    struct Node *next;
};
typedef struct Node Node;

int find_largest_le_fib_n(int n) {
    if (n == 0 || n == 1) {
       return n;
    }

    int f1 = 0, f2 = 1, f3 = 1;

    while (f3 <= n) {
        f1 = f2;
        f2 = f3;
        f3 = f1 + f2;
    }

    return f2;
}

Node* find_zeckendorf(int n) {
    Node *last;
    Node *first;
    Node *penultimate = NULL;

    int largest_le_fib;

    while (n > 0) {
        largest_le_fib = find_largest_le_fib_n(n);

        last = malloc(sizeof(Node));        
        last->data = largest_le_fib;
        last->next = NULL;

        if (first == NULL) {
            first = last;
        }
        
        if (penultimate != NULL) {
            penultimate->next = last;
        }

        penultimate = last;

        n -= largest_le_fib;
    }

    return first;
}

int main() {
    int n = 0;

    printf("Enter number: ");
    scanf("%d", &n);

    Node *zeckendorf_list = find_zeckendorf(n);

    while (zeckendorf_list != NULL) {
        printf("%d ", zeckendorf_list->data);

        Node *temp = zeckendorf_list;
        zeckendorf_list = zeckendorf_list->next;
        free(temp);
    }

    printf("\n");
}

Example run:

Enter number: 100
89 8 3 

(More test cases can be found in the mark scheme)

I would be grateful to hear about any improvements that could be made to this code.

Answer 1

Review:

Again, nice looking code that does what it is supposed to do. Well presented and fairly easy to follow. Kudos!

But, the exercise states "in any order", so much of the clerical code (that is correct, too) dealing with heap memory and a linked list is, in fact, a distraction.

---

Since the exercise is to generate the list of numbers only, the following (distilled from your code) is presented here for your learning and appraisal.

#include <stdio.h>

int find( int n ) {
    if( n == 1 ) return n;

    int f1 = 1, f2 = 2; // tiny shortcut as problem suggests
    while( f1 + f2 <= n ) {
        int fx = f1 + f2;
        f1 = f2;
        f2 = fx;
    }

    return f2;
}

int main( void ) {
    int n = 0;

    for( ;; ) { // infinite loop for testing many numbers
        printf("Enter number: ");
        if( scanf( "%d", &n ) != 1 ) { // check return codes!
            scanf( "%*[^\n]" ); // clear the input buffer. (read scanf doco!)
            continue;
        }

        for( int large; n; n -= large )
            printf( "%d ", large = find( n ) ); // output is all that's required
        puts( "" );
    }

    return 0;
}

Here's an abridged list of some Fibonacci numbers

       0   #01
       1   #02
...
  832040   #31
 1346269   #32 // Bigger than the problem's 1000000 limit

Output:

Enter number: 832039
514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2
Enter number:

---

Now that we know there are 31 Fibonacci numbers between 0 and 1000000, a simple array of int store[31] would more-than serve to store and print the found values of interest for this exercise.

Were such an array to be populated once at startup (only to the limit of interest for 'single shot' or to the 1000000 limit for multiple queries) determination of the Zeckendorf representation values to be printed would be greatly accelerated.

Your code is very good. A lesson that will be valuable going forward is to only write correct code to meet today's requirements. Some suggest coding in certain (costly) ways "in case the demands change tomorrow." Let tomorrow take care of itself. Take care that the user typing "foo", instead of 15642, doesn't cause your program to collapse in a pool of tears.

---

Poor man's profiling

Enter number: 832039
..........................514229 ........................196418 ......................75025 ....................28657 ..................10946 ................4181 ..............1597 ............610 ..........233 ........89 ......34 ....13 ..5 2

Simply adding putchar( '.' ); inside the function's while() loop, we can see the effect of recalculating the (shortened) Fibonacci sequence values to find these desired values. And this is the 'ceiling' of only 10⁶ (considering only the first ~30 Fibonacci numbers).

Eventually, a long long will be necessary to go for more Fibonacci numbers. Given the finite maximums of a long and a long long, what are the maximum Fibonacci numbers that can be represented without recourse to more advanced techniques of representing very large integer values? Would it be worthwhile calculating as many of these constants as possible ONE TIME, then having those as a compile time array of values to use for this and other explorations of number theory?

(FYI: There are 182 dots (iterations) in that 'profiling' string, and there should be about 28 more if the function didn't shortcut by skipping 0+1 and 1+1.)

---

Added interest

With the recent posting of a very compact Python solution of the OP's problem, it behooves C to also present its possibilities of concise expression: C here

Answer 2

• Node *first; shall be Node *first = NULL;. Otherwise, a test for first == NULL invokes UB.

• find_largest_le_fib_n is redoing the same work over and over again. It seems better to precompute an array of Fibonacci numbers in the range of 1,000,000 once, and binary search it. You can even do it off-line - there are not too many of them.

• malloc may fail. Make sure to test its return value.

• The problem statement does not specify an order of numbers in the representation. An example says 3 8 89, while your code produces 89 8 3. If such order is OK, you don't need a linked list at all.

Answer 3

In my opinion you did not just choose an unnecessarily complicated algorithm/implementation but also an unnecessarily complicated language. In that round, "any language" was allowed. And you only had three hours and there were lots more questions, so better keep it simple to save time.

Simpler algorithm/implementation in a simpler language (Python, Attempt This Online!):

n = int(input())
while n:
    a, b = 1, 2
    while b <= n:
        a, b = b, a+b
    print(a, end=' ')
    n -= a

Although the equivalent C version isn't that much longer (Attempt This Online!):

#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  while (n) {
    int a = 1, b = 2;
    while (b <= n) {
      int sum = a + b;
      a = b;
      b = sum;
    }
    printf("%d ", a);
    n -= a;
  }
}

More efficient algorithm (really not needed, though, as it is super fast already) without a list, instead reversing the calculation (Attempt This Online!):

n = int(input())
a, b = 1, 2
while b <= n:
    a, b = b, a+b
while n:
    if a <= n:
        print(a, end=' ')
        n -= a
    a, b = b-a, a