Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorFabinocci Numbers with matrix multiplication
LEVEL:Beginner
Description
For the given input print the nth number in the fabinocii series
Input Format
Single line contains n
Output Format
Print the nth number in the fabinocci series
1
0
2
1
3
1
Login to see Discussion
Approach
i)create a method multiply which multiplies the two 2 dimensional arrays and store the values in the first array
ii)create a another method power
iii)if n equal to 0 or 1 just return
iv)else create a 2d array and assign 1 1 1 0 to it respectively
v)call the function power with F and n/2
vi)then multiply F and F matrix
vii)if n is even again multiply F and M
viii)create a method fabinocii matrix
ix)create a 2 d array initialize with 1 1 1 0 call the power function with F and n-1 and return first elemetn of the matrix
x)in main method take the required input and print the output
Time Complexity: O(log n)
Space Complexity: O(1)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution