class Solution {
public:
    int fib(int n) {
        if (n==0)
        return 0;
        if (n==1)
        return 1;
        return fib(n-1)+fib(n-2);
        
    }
};

const int mod = 1e9+7;
void multiply(long long int F[2][2], long long int M[2][2]);
void power(long long int F[2][2], long long int n);

int fib(long long int n)
{
    long long int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0) return 0;
    power(F, n - 1);
    return F[0][0];
}
void power(long long int F[2][2], long long int n)
{
    if(n == 0 || n == 1) return;

    long long int M[2][2] = {{1, 1}, {1, 0}};
    
    power(F, n / 2);
    multiply(F, F);
    
    if (n % 2 != 0)
        multiply(F, M);
}
void multiply(long long int F[2][2], long long int M[2][2])
{
    int x = ((F[0][0]%mod * M[0][0]%mod)%mod + (F[0][1]%mod * M[1][0]%mod)%mod)%mod;
    int y = ((F[0][0]%mod * M[0][1]%mod)%mod + (F[0][1]%mod * M[1][1]%mod)%mod)%mod;
    int z = ((F[1][0]%mod * M[0][0]%mod)%mod + (F[1][1]%mod * M[1][0]%mod)%mod)%mod;
    int w = ((F[1][0]%mod * M[0][1]%mod)%mod + (F[1][1]%mod * M[1][1]%mod)%mod)%mod;
    
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
// call using fib(n)

function flatten(arr) {
  let flat = []
  
  for(let prop of arr){
    if(Array.isArray(prop)){
      flat.push(...flattan(prop))
    } else {
      flat.push(prop)
    }
  }
  return flat
}

function getSubstringCount(s) {
    // Write your code here
    let [current, prev, result] = [1, 0, 0]
    
    for(let i=1; i<s.length; i++){
        let left = s[i-1]
        let right = s[i]
        if(left == right){
            current++
        } else {
            prev = current
            current = 1
        }
        if(prev >= current){
            result++
        }
    }
    return result
}

//find fibonacci numbers

function fib(n){
  if(n >=3 ){
    return fib(n-1) + fib(n-2)
  } else {
    return 1;
  }
}

console.log(fib(10))

// Time Complexity: O(2^n), Auxiliary Space: O(N).
// Fibonacci Series using Recursion

class fibonacci
{
	static int fib(int n)
	{
      // if (n == 0) return 0;
      // if (n == 1) return 1;
      if (n <= 1)
      	return n;
      
      return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
      int n = 9;
      System.out.println(fib(n));
	}
}

//First Examples
function fibonacci(n) {
	const list = [0, 1];
	for (let x = 2; x < n + 1; x += 1) {
		list.push(list[x - 2] + list[x - 1]);
	}
	return list[n];
}

console.log(fibonacci(4));

//Second Examples
function fibonacci(nums) {
  
  let fib = [0, 1];
  let data = [];
  
  for(let i = 2; i <= nums; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]; 
    data.push(fib[i]);
  }
  
  return data;
}

//Third Examples
function fibonacci(nums) {
  
  let fib = [0, 1];
  let data = [];
  
  for(let i = 2; i <= nums; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]; 
    data.push(fib[i]);
  }
  
  return data;
}

#include <iostream>  
using namespace std;  
int main() 
{  
  int n1=0,n2=1,n3,i,number;    
 cout<<"Enter the number of elements: ";    
 cin>>number;    
 cout<<n1<<" "<<n2<<" "; //printing 0 and 1    
 for(i=2;i<number;++i) //loop starts from 2 because 0 and 1 are already printed    
 {    
  n3=n1+n2;    
  cout<<n3<<" ";    
  n1=n2;    
  n2=n3;    
 }    
   return 0;  
}