JavaScript Coding Test Course, Calculating Number of Stairs

Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called “Counting Stair Numbers”. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies.

Problem Description

A stair number refers to a number of n digits where the difference between two adjacent digits is 1. For example, numbers like 123 and 321 are stair numbers since the difference between adjacent digits is 1. Write a program to find the n-digit stair numbers for the given n.

Input

An integer n (1 ≤ n ≤ 1000)

Output

Output the number of n-digit stair numbers modulo 1,000,000,000.

Problem Solving Strategy

To solve this problem, we can use a dynamic programming approach. Stair numbers can be defined by the following state:

• dp[i][j]: the number of i-digit stair numbers that end with j

The rules for forming stair numbers can be established as follows:

• When j is 0 (no number can start with 0): dp[i][0] = dp[i-1][1]
• When j is 9: dp[i][9] = dp[i-1][8]
• In other cases: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

Initialization of the Dynamic Programming Table

Now let’s initialize the dp table. For 1-digit numbers, since digits can range from 0 to 9, we initialize dp[1][0] to dp[1][9] to 1 respectively.

Solution Code

function countStairNumbers(n) {
    const MOD = 1000000000;
    const dp = Array.from({ length: n + 1 }, () => Array(10).fill(0));

    // Initialize 1-digit numbers
    for (let j = 0; j < 10; j++) {
        dp[1][j] = 1;
    }

    // Fill the dp table
    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            if (j > 0) dp[i][j] += dp[i - 1][j - 1]; // Move from j-1
            if (j < 9) dp[i][j] += dp[i - 1][j + 1]; // Move from j+1
            dp[i][j] %= MOD; // modulo operation
        }
    }

    // Sum of all n-digit stair numbers
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[n][j];
    }

    return result % MOD;
}

// Example of function call
console.log(countStairNumbers(3)); // 24

Time Complexity

The time complexity of the above code is O(n), and the space complexity is O(n). Since the result is derived through combinations of each digit, it efficiently uses time and space as n increases.

Optimization Strategies

To reduce memory usage in the currently implemented code, we can change the dp array from two-dimensional to one-dimensional. Since only the previous dp state is needed for each i, this can be utilized for optimization.

function countStairNumbersOptimized(n) {
    const MOD = 1000000000;
    const dp = Array(10).fill(0);
    const temp = Array(10).fill(0);

    // Initialize 1-digit numbers
    for (let j = 0; j < 10; j++) {
        dp[j] = 1;
    }

    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            temp[j] = 0;
            if (j > 0) temp[j] += dp[j - 1]; // Move from j-1
            if (j < 9) temp[j] += dp[j + 1]; // Move from j+1
            temp[j] %= MOD; // modulo operation
        }
        for (let j = 0; j < 10; j++) {
            dp[j] = temp[j]; // Update for the next step
        }
    }

    // Sum of all n-digit stair numbers
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[j];
    }

    return result % MOD;
}

Conclusion

In this article, we learned how to solve the “Counting Stair Numbers” problem using dynamic programming in JavaScript. I provided a detailed explanation of initialization, constructing the dp table, and the optimization process, as well as methods to enhance the efficiency of the algorithm through various techniques. When solving algorithm problems, always consider multiple approaches and explore ways to optimize them. Thank you!