Competitive Programming Solutions

O. Fibonacci

Codeforces - Sheet #7 (Recursion) · limit: 1s · memory: 256MB · view on codeforces

input

output

Main.java

static void solve() {

        // Write your solution here
        int n = in.nextInt();
        out.println(fibb(n - 1));
    }

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static final int MOD2 = 998_244_353;
    static final Random rnd = new Random();

    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int t = 1;
        // Comment if program has single input
        // t = in.nextInt();
        while (t-- > 0) {
            solve();
        }
        out.flush();
    }

    static void solve() {

        // Write your solution here
        int n = in.nextInt();
        out.println(fibb(n - 1));
    }

    static long fibb(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;

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

    // =========================
    // Array Input
    // =========================

    static int[] readIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();
        return a;
    }

    static long[] readLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextLong();
        return a;
    }

    // =========================
    // Safe Sort
    // =========================

    static void safeSort(int[] a) {
        shuffle(a);
        Arrays.sort(a);
    }

    static void safeSort(long[] a) {
        shuffle(a);
        Arrays.sort(a);
    }

    static void shuffle(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            int j = rnd.nextInt(i + 1);
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    static void shuffle(long[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            int j = rnd.nextInt(i + 1);
            long temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    // =========================
    // Math
    // =========================

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    static long power(long base, long exp, long mod) {
        long ans = 1;
        base %= mod;

        while (exp > 0) {
            if ((exp & 1) == 1)
                ans = (ans * base) % mod;

            base = (base * base) % mod;
            exp >>= 1;
        }

        return ans;
    }

    // =========================
    // Reverse
    // =========================

    static void reverse(int[] a) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            int temp = a[l];
            a[l++] = a[r];
            a[r--] = temp;
        }
    }

    static void reverse(long[] a) {
        int l = 0, r = a.length - 1;
        while (l < r) {
            long temp = a[l];
            a[l++] = a[r];
            a[r--] = temp;
        }
    }

    // =========================
    // Fast Reader
    // =========================

    static class FastReader {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
}