LeetCode: C# fibonacci number iterative solution

Question

https://leetcode.com/problems/fibonacci-number/

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n).

Example 1:

Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1. Example 2:

Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2. Example 3:

Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

here is my solution is there a way to reduce memory foot print?

public class Solution {
 public int Fib(int n) {
 if (n == 0)
 {
 return 0;
 }
 if (n == 1)
 {
 return 1;
 }
 int a = 0;
 int b = 1;
 int c = 0;
 for(int i = 2; i <= n; i++) /
 { 
 c = a+b; 
 a = b; 
 b = c; 
 }
 return c;
 }
}

• Peter Csala: I know it is coding challenge so naming does not matter, but I think it is a good practice if you try to force yourself to come up with meaningful names even in such program like this.

Answer 1

Yes you can save some memory by getting rid of i in for loop and working with input n. Although it's not good practice to change input parameters.

int a = 1;
int b = 1;
int c = 1;
for(; n > 2; n--)
{ 
 c += a; 
 a = b; 
 b = c; 
}

I got insteresting results by using .NET 6 and BenchmarkDotNet (I'm not benchmarking/memory expert so take it with a pinch of salt) - for Fib(30):

Method	Mean	Error	StdDev	Gen 0	Allocated
Optimized	14.79 ns	0.319 ns	0.283 ns	-	-
Original	25.29 ns	0.544 ns	0.994 ns	0.0153	24 B

Answer 2

The Fibonacci sequence can be written in the form $$\displaystyle \frac{\varphi^n-\psi^n}{\sqrt{5}}\text{, where}$$ $$\varphi = \frac{1+\sqrt{5}}{2} \approx 1.61803 39887 \cdots$$ $$\text{Is the golden ratio, and}$$ $$\psi = \frac{1 - \sqrt{5}}{2} \approx -0.61803 39887 \cdots$$ $$\text{and since}$$ $$\psi = -\varphi^{-1}$$ $$\text{this formula can be written as}$$ $$\displaystyle F_n = \frac{\varphi^n- \left(-\varphi\right)^{-n}}{2\varphi-1}$$ For example, let n = 15, we would then have $$\displaystyle \frac{\varphi^{15} - (-\varphi)^{-15}}{2\varphi-1} = 610$$

We can implement this in C# as

 private static readonly double phi = (1 + Math.Sqrt(5)) / 2; 
 private static readonly double twoPhiMinusOne = 2 * phi - 1; 
 private static int Fib(int n) => Convert.ToInt32((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / twoPhiMinusOne);

Which will completely remove the need for a loop.

• Rick Davin: This is a nice answer but you should put guard clauses to make sure than n is >= 0. Also, you do not do anything with variable psi as it is not referenced in your return expression.
• Jesse C. Slicer: Pull out some constants so they're not re-calculated every time: private static readonly double phi = (1 + Math.Sqrt(5)) / 2; private static readonly double twoPhiMinusOne = 2 * phi - 1; private static int Fib(int n) => Convert.ToInt32((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / twoPhiMinusOne);