14.25 Custom Fibonacci Sequence

14.25.1 Metadata

  • Platform: HackerRank
  • Problem ID: custom-other-fibonacci-sequence
  • Difficulty: Easy
  • URL: Custom Fibonacci Sequence
  • Tags:
  • Techniques: Dynamic Programming (Tabulation)

14.25.2 Description

Given n (0-based indexing), return the n-th Fibonacci number where F(0) = 1, F(1) = 2, and F(n) = F(n-1) + F(n-2).

14.25.3 Examples

Example 1:

Input:

n = 3

Output:

5

Explanation:

Compute intervals step by step: interval[0] = 1, interval[1] = 2. Then interval[2] = 1 + 2 = 3, interval[3] = 2 + 3 = 5. So for n = 3, the function returns 5.

Example 2:

Input:

n = 10

Output:

144

Explanation:

List the first 11 intervals: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]. Each interval is the sum of the two previous ones. The 10th index (0-based) is 144.

14.25.4 Constraints

  • \(0 \le n \le 92\)
  • n is an integer

14.25.5 Walkthrough

This problem is a variant of the classic Fibonacci sequence with custom starting values: F(0) = 1 and F(1) = 2, instead of the traditional F(0) = 0 and F(1) = 1.

Key Observations:

  1. The recurrence relation remains the same: F(n) = F(n-1) + F(n-2)
  2. Only the base cases differ from the standard Fibonacci sequence
  3. We can use 14.0.1">dynamic programming to build up the solution from the base cases

Approach:

Use a bottom-up dynamic programming approach with tabulation:

  1. Handle base cases directly: if n is 0, return 1; if n is 1, return 2
  2. Create a DP array of size n+1 to store computed Fibonacci values
  3. Initialize dp[0] = 1 and dp[1] = 2
  4. Iterate from index 2 to n, computing each value as the sum of the previous two
  5. Return dp[n] as the final answer

Example trace for n = 3:

dp[0] = 1
dp[1] = 2
dp[2] = dp[1] + dp[0] = 2 + 1 = 3
dp[3] = dp[2] + dp[1] = 3 + 2 = 5

Return 5.

14.25.6 Analysis

Time Complexity: \(O(n)\)

We iterate through the array once from index 2 to n, performing constant-time operations at each step.

Space Complexity: \(O(n)\)

We use a DP array of size n+1 to store all Fibonacci values from 0 to n.

Optimization Note:

The space complexity can be optimized to \(O(1)\) by observing that we only need the previous two values at any point. Instead of maintaining an entire array, we can use two variables to track F(n-1) and F(n-2), updating them in each iteration. However, for the given constraints (\(n \le 92\)), the current solution is efficient and more readable.

14.25.7 Implementation Steps

  1. Handle base cases:
    • If \(n < 1\), return 1 (F(0) = 1)
    • If \(n < 2\), return 2 (F(1) = 2)
  2. Initialize DP array:
    • Create long array dp of size n+1 (use long to handle large Fibonacci numbers)
    • Set dp[0] = 1
    • Set dp[1] = 2
  3. Build up the solution:
    • For each index i from 2 to n:
      • Compute dp[i] = dp[i-1] + dp[i-2]
  4. Return result:
    • Return dp[n]

14.25.8 Java Code

class Result {

    /*
     * Complete the 'getAutoSaveInterval' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts INTEGER n as parameter.
     */

    public static long getAutoSaveInterval(int n) {
        // Base case: F(0) = 1
        if (n < 1) {
            return 1;
        }

        // Base case: F(1) = 2
        if (n < 2) {
            return 2;
        }

        // Initialize DP array
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 2;

        // Build up Fibonacci values using recurrence relation
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

}

Space-Optimized Alternative (O(1) space):

public static long getAutoSaveInterval(int n) {
    if (n < 1) return 1;
    if (n < 2) return 2;

    long prev2 = 1;  // F(n-2)
    long prev1 = 2;  // F(n-1)

    for (int i = 2; i <= n; i++) {
        long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}