CodingGyan

Climbing Stairs

easy Data Structures and Algorithms

Problem

You climb a staircase with n steps. Each time you can climb 1 or 2 steps. Read n and print the number of different ways to reach the top.

Constraints

  • 1 <= n <= 45

Examples

Input

3

Output

3

Solutions

Best approachTime O(n)Space O(1)

The last move was either 1 step or 2 steps. So the number of ways to reach step n is the sum of the ways to reach the two steps before it. This is the Fibonacci sequence, and two variables are enough.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count the ways to climb.
 * Input   : One integer n.
 * Output  : The number of ways.
 * Approach: ways(n) = ways(n-1) + ways(n-2).
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: ways(0) = 1 and ways(1) = 1. To reach step i, you come from step i - 1 or step i - 2.
        long previous = 1;
        long current = 1;

        // Step 2: ways(i) = ways(i - 1) + ways(i - 2). We only keep the last two values.
        for (int i = 2; i <= n; i++) {
            long next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. From which two steps can you reach step n?

Try these next