Long Luo's Life Notes

By Long Luo

The \(\textit{Fibonacci Sequence}\)¹ are the numbers in the following integer sequence:

\(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \dots\)

We can see the fibonacci series seqences in the natrual world like the sunflower, the nautilus and the galaxy.

In mathematical terms, the sequence \(F(n)\) of Fibonacci numbers is defined by the recurrence relation

\[ F(n) = F(n-1) + F(n-2) \]

with seed values \(F(0) = 0\) and \(F(1) = 1\).

The Fibonacci sequence is often used in introductory computer science courses to explain recurrence relations, dynamic programming, and proofs by induction. Because the Fibonacci sequence is central to several core computer science concepts, the following programming problem has become fairly popular in software engineering interviews.

Given an input \(n\), return the \(nth\) number in the Fibonacci sequence.

Below I’ve listed \(9\) approaches to this problem. These different solutions illustrate different programming and algorithmic techniques that can be used to solve other problems. You’ll notice that many of these solutions build from previous solutions.

Solution 1 Lookup Table - 32 bit signed integers only

If we don’t need to solve very large values and are time-sensitive, we can calculate all values in advance.

This function will work strictly in the case that we’re dealing with \(32\) bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)

The Fibonacci sequence grows very quickly. So fast, that only the first \(47\) Fibonacci numbers fit within the range of a \(32\) bit signed integer. This method requires only a quick list lookup to find the nth Fibonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    int[] fib_nums = {
            0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
            6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
            1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
            102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
    };

    public int fib(int n) {
        return fib_nums[n];
    }
};

Analysis

• Time Complexity: \(O(1)\)
• Space Complexity: \(O(1)\)

Solution 2 Recursion

A simple method that is a direct recursive implementation mathematical recurrence relation is given above.

1
2
3
4
5
6
7
8

//Fibonacci Series using Recursion
public static int fib(int n) {
	if (n <= 1) {
		return n;
	}

	return fib(n - 1) + fib(n - 2);
}

Analysis

• Time Complexity: \(O(\phi^n)\), where \(\phi\) is the golden ratio (\(\phi \simeq 1.618...\)).

If we count the number of calls that this algorithm makes for any n, we will find its runtime complexity.

Let \(T(n)\) refer to the number of calls to fib1 that are required to evaluate fib1(n).

When fib1(0) or fib1(1) is called, fib1 doesn’t make any additional recursive calls, so \(T(0)\) and \(T(1)\) must equal 1.

For any other n, when fib1(n) is called, fib1(n - 1) and fib1(n - 2) are also called.

So

\[ T(n) = 1 + T(n - 1) + T(n - 2) \]

Using more advanced mathematical techniques, like generating functions, one can solve the recurrence \(T\), and find that \(T\) scales as \(O(\phi)\).

If the original recursion tree were to be implemented then this would have been the tree but now for n times the recursion function is called.

Original tree for recursion:

1
2
3
4
5
6
7
8
9

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

Optimized tree for recursion for code above:

1
2
3
4
5

fib(5) 
fib(4)
fib(3)
fib(2)
fib(1)

• Space Complexity: \(O(n)\) if we consider the function call stack size, otherwise \(O(1)\).

By Long Luo

This article is the solution 2 Approaches: Base Conversion from High to Low and from Low to High of Problem 171. Excel Sheet Column Number.

Intuition

Basiclly, It’s base conversion.

We are familiar base \(10\). How do we calculate a number?

From high to low, starting with \(ans\) as \(0\), update \(ans\) with the current digit value each time, the update rule is \(ans = ans \times 10 + val\).

If there is a decimal number, encoded as \(\textit{ABC}\) not the arabic number, what’s it?

1
2
3
4

ans = 0
ans = ans * 10 + 1  => A
ans = ans * 10 + 2  => B
ans = ans * 10 + 3  => C

The answer is: \(123\).

from High to Low

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int titleToNumber(String columnTitle) {
    int n = columnTitle.length();
    int ans = 0;
    int base = 1;
    for (int i = n - 1; i >= 0; i--) {
        int temp = 0;
        if (columnTitle.charAt(i) == 'Z') {
            temp = 26;
        } else {
            temp = columnTitle.charAt(i) - 'A' + 1;
        }
        ans = ans + base * temp;
        base *= 26;
    }

    return ans;
}

By Long Luo

This article is the solution 3 Approaches: Brute Force, HashMap and Sliding Window of Problem 219. Contains Duplicate II.

Here are \(3\) approaches to solve this problem in Java, which is Brute Force, HashMap and Sliding Window.

Brute Force

Easy, using \(2\) loops to determine whether there is the same number.

obviously, it will time out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                if (Math.abs(i - j) <= k) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

HashMap

We use a \(\texttt{HashMap}\) to record the maximum index of each element. When scanning the array from left to right, the process:

• If an element \(\textit{nums}[i]\) already exists in the hash table and the index \(j\) of the element recorded in the hash table satisfies \(abs(i - j) \le k\), return \(\text{true}\);

• Recording \(\textit{nums}[i]\) and index \(i\) into the hash table, where \(i\) is the largest index of \(\textit{nums}[i]\).

The order of the above two-step operations cannot be changed, when the index \(i\) is traversed, the element equal to the current element and the maximum index of the element can only be found in the elements before the index \(i\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; i++) {
        if (map.containsKey(nums[i])) {
            int idx = map.get(nums[i]);
            if (Math.abs(i - idx) <= k) {
                return true;
            }
            map.put(nums[i], i);
        } else {
            map.put(nums[i], i);
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

By Long Luo

This article is the solution 4 Approaches: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method of Problem 69. Sqrt(x) .

Here shows 4 approaches for finding the square root of a number: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method.

Given an integer \(N\) and a tolerance level \(L\), the task is to find the square root of that number.

Brute Force

The Brute Force way is very easy, just enumerate a value from \(0\) to \(x\), check the product \(i^2\) and target, return the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int mySqrt(int x) {
    if (x == 0 || x == 1) {
        return x;
    }

    for (int i = 0; i < x; i++) {
        long sum = i * i;
        long bigger = (long) (i + 1) * (i + 1);
        if (sum == x) {
            return i;
        } else if (sum < x && bigger > x) {
            return i;
        }
    }

    return 0;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

Exponent

Noted that:

\[ \sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x} \]

So we can use the exponent \(\exp\) and logarithm \(\ln\) to calculate the square root of the number \(\sqrt{x}\).

It’s really a fast and simple way!

Note: Since the computer can’t store the exact value of the float number, and the parameters and return values of the exponential function and logarithmic function are float numbers, so the result may be wrong.

For example, when \(x = 2147395600\), the result of \(e^{\frac{1}{2} \ln x}\) is \(10^{-11}\) from the correct value of \(46340\) , so when taking the integer part of the result, you will get the wrong result of \(46339\) .

So after getting the integer part \(\textit{ans}\) of the result, we should find out which of \(\textit{ans}\) and \(\textit{ans} + 1\) is the real answer.

1
2
3
4
5
6
7
8

// Exp O(1) O(1)
public static int mySqrt_exp(int x) {
    if (x == 0) {
        return 0;
    }
    int ans = (int) Math.exp(0.5 * Math.log(x));
    return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}

Analysis

• Time Complexity: \(O(1)\)
• Space Complexity: \(O(1)\).

By Long Luo

This article is the solution Fast Power Algorithm: Binary Exponentiation of Problem 50. Pow(x, n) .

We know how to find \(2.0\) raised to the power \(10\). The easiest way is to multiply \(10\) times \(2.0\) by loop, but what if we have to find \(2.0\) raised to the power very large number such as \(10000\) or more?

We will discuss how to find the solution of such problems by using an fast, efficient algorithm.

Brute Force

We multiply \(a\) to itself \(b\) times. That is, \(a^b = \underbrace{a \times a \dots \times a}_b\).

A simple java implementation of that would be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public static double myPow(double x, int n) {
    if (n == 0 || x == 1) {
        return 1;
    } else if (x == 0) {
        return 0;
    }

    double ans = x;
    boolean isNegative = false;
    long nLong = n;
    if (nLong < 0) {
        nLong = -nLong;
        isNegative = true;
    }

    for (int i = 1; i < nLong; i++) {
        ans = ans * x;
    }

    if (isNegative) {
        ans = 1 / ans;
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)