Fibonacci Matrix Multiplication O(logn)

#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;  
}  

//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;
}

// 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));
	}
}

//find fibonacci numbers

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

console.log(fib(10))

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
}

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

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)

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

class GFG 
{ 
	static int R = 4, C = 4;
	static void printSnake(int mat[][])
	{
		for(int i = 0; i < R; i++)
		{
			if(i % 2 == 0)
			{
				for(int j = 0; j < C; j++)
					System.out.print(mat[i][j] + " ");
			}
			else
			{
				for(int j = C - 1; j >= 0; j--)
					System.out.print(mat[i][j] + " ");
			}
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSnake(arr);
    } 
}

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

class GFG 
{ 
	static int R = 4, C = 4;

	static void bTraversal(int mat[][])
	{
		if(R == 1)
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
		}
		else if(C == 1)
		{
			for(int i = 0; i < R; i++)
				System.out.print(mat[i][0] + " ");
		}
		else
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
			for(int i = 1; i < R; i++)
				System.out.print(mat[i][C - 1] + " ");
			for(int i = C - 2; i >= 0; i--)
				System.out.print(mat[R - 1][i] + " ");
			for(int i = R - 2; i >= 1; i--)
				System.out.print(mat[i][0] + " ");
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	bTraversal(arr);
    } 
}

// Efficient Code : Without Using Auxiliary Array

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

class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}

	static void transpose(int mat[][])
	{

		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	transpose(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    } 
}




// Naive Code : 

	static int n = 4;

	static void transpose(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy
				temp[i][j] = mat[j][i]; // temp[i][j] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy back to original array
				mat[i][j] = temp[i][j];

	}

// Efficient Code : Time Complexity : O(n^2), Auxiliary Space : O(1)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}
	
	static void swap2(int low, int high, int i, int mat[][])
	{
	    	int temp = mat[low][i];
			mat[low][i] = mat[high][i];
			mat[high][i] = temp;
	}

	static void rotate90(int mat[][])
	{
		// Transpose
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
      
		// Reverse columns		
		for(int i = 0; i < n; i++)
		{
		    int low = 0, high = n - 1;
		    
		    while(low < high)
		    {
		        swap2(low, high, i, mat);
		        
		        low++;
		        high--;
		    }
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	rotate90(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    }
}
 
 
 
 
// Naive Code : Time Complexity : O(n^2), Space Complexity : O(n^2)
 
	static int n = 4;

	static void rotate90(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				temp[n - j - 1][i] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				mat[i][j] = temp[i][j];

	}

// last column becomes first row
// second last column becomes second row

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

class GFG 
{ 
	static void printSpiral(int mat[][], int R, int C)
	{
		int top = 0, left = 0, bottom = R - 1, right = C - 1;

		while(top <= bottom && left <= right)
		{
			for(int i = left; i <= right; i++)
				System.out.print(mat[top][i] + " ");

			top++;

			for(int i = top; i <= bottom; i++)
				System.out.print(mat[i][right] + " ");
			
			right--;

			if(top <= bottom){
			for(int i = right; i >= left; i--)
				System.out.print(mat[bottom][i] + " ");

			bottom--;
			}

			if(left <= right){
			for(int i = bottom; i >= top; i--)
				System.out.print(mat[i][left] + " ");

			left++;
			}			
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSpiral(arr, 4, 4);
    } 
}

// Efficient Code : Time Complexity : O(R + C)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		int i  = 0, j = C - 1;

		while(i < R && j >= 0)
		{
			if(mat[i][j] == x)
			{
				System.out.println("Found at (" + i + ", " + j + ")");
				return;
			}
			else if(mat[i][j] > x)
			{
				j--;
			}
			else
			{
				i++;
			}
		}
		System.out.println("Not Found");
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{10, 20, 30, 40},
    				   {15, 25, 35, 45},
    				   {27, 29, 35, 45},
    				   {32, 33, 39, 50}};
    	int x = 29;	   

    	search(arr, x);

		
    } 
}
 
 
 
 
// Naive Code : Time Complexity : O(R * C)
 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		for(int i = 0; i < R; i++)
		{
			for(int j = 0; j < C; j++)
			{
				if(mat[i][j] == x)
				{
					System.out.println("Found at (" + i + ", " + j + ")");
					
					return;
				}
			}
		}

		System.out.println("Not Found");
	}

// Time Complexity : O(r * log(max - min) * logC)

import java.util.Arrays;

public class MedianInRowSorted
{
    static public int matMed(int mat[][], int r ,int c)
    {
    	int min = mat[0][0], max = mat[0][c-1];
    	for (int i=1; i<r; i++)
    	{
    		if (mat[i][0] < min)
    			min = mat[i][0];
    
    		if (mat[i][c-1] > max)
    			max = mat[i][c-1];
    	}
    
    	int medPos = (r * c + 1) / 2;
    	while (min < max)
    	{
    		int mid = (min + max) / 2;
    		int midPos = 0;
            int pos = 0;
    		for (int i = 0; i < r; ++i){
    			    pos = Arrays.binarySearch(mat[i],mid);
                    
                    if(pos < 0)
                        pos = Math.abs(pos) - 1;
                      
                    
                    else
                    {
                        while(pos < mat[i].length && mat[i][pos] == mid)
                            pos += 1;
                    }
                      
                    midPos = midPos + pos;
    		}
    		if (midPos < medPos)
    			min = mid + 1;
    		else
    			max = mid;
    	}
    	return min;
    }

    public static void main(String[] args)
    {
    	int r = 3, c = 5;
    	int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
    	System.out.println("Median is " + matMed(m, r, c)); 
    	
    }
}

class Solution
{
    //Function to add two matrices.
    static int[][] sumMatrix(int A[][], int B[][])
    {
        int n = A.length, m = A[0].length;
        int res[][] = new int[0][0];
        //Check if two input matrix are of different dimensions
        if(n != B.length || m != B[0].length)
            return res;
        
        res = new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                res[i][j] = A[i][j] + B[i][j];
                
        return res;
    }
}