SPOJ ASCDFIB – Ascending Fibonacci Numbers is one of the earliest problems I created. This problem was used in one of the internal contests of Daffodil University. I was aiming for an easy, but a tricky problem and thus the following problem was created.

Problem

Read the complete description of the problem from SPOJ ASCDFIB – Ascending Fibonacci Numbers.

Before you continue reading the rest of the post, please try to solve the problem on your own.

Problem Summary

• Given $A \leq 10^5$ and $B \leq 10^6$
• Print from $fib(A)$ to $fib(A+B)$ in ascending order.
• $fib(n)$ is $n_{th}$ fibonacci number mod $10^5$.
• If there are more than $100$ terms in output, we need to print just the first $100$.
• There are $100$ test cases.
  

Solution

1. First calculate value of $fib(A)$ using $O(A)$ loop.
2. Next, using a $O(B)$ loop, generate all terms from $fib(A)$ to $fib(A+B)$ and store them in an array $V$.
3. Sort the array $V$ and print the first $100$ terms.

Simple right? But there is a catch. What is the complexity of the third step?

If you use normal built-in sort function, then the complexity of the third step will be $O(B \times logB)$. And this is too slow for the current problem since there are $100$ test cases.

Notice that all the value in the array $V$ is smaller than $10^5$ since we are using the mod value. As such, we can use counting sort to sort the array in $O(B)$ complexity. And this is the trick to solving the problem.

If you don’t know how counting sort works, watch the following video:

Using counting sort, our overall complexity for the solution becomes $O(B)$, which is fast enough to get AC.

Conclusion

When creating this problem, I was hoping that people won’t be aware of $O(N)$ sorting algorithms. And for those who know the counting sort algorithm, I was hoping they won’t remember about it since it’s not very usual to have a problem that revolves around counting sort. Well, I hope the same for my readers :p

Let me know what you thought about the problem. Did you get TLE?

Reference

1. Problem Link: SPOJ ASCDFIB – Ascending Fibonacci Numbers
2. Counting Sort Video: Counting Sort | GeeksforGeeks

• Category: CPPS, Data Structure
• Tag: editorial