🔴 SheCodes Express is now LIVE: it’s a free, 60-minute coding session for beginners.
Join class NOW 👉
Watch
Find fibonacci number example : fibo of 0 = 1 fibo of 1 = 1 fibo of 2 = fibo 0 + fibo 1 = 2 fibo of 3 = fibo 2 + fibo 1 = 3 fibo of 4 = fibo 3 + fibo 2 = 5 fibo of 5 = fibo 4 + fibo 3 = 8 write function int fibo(int number) -> return fibo value of paramerter. write code with possible small time complexity
java Copy code
public int fibo(int number) {
if (number <= 1) { // Base cases for fibonacci series
return 1;
}
int prev1 = 1, prev2 = 1, fibo = 1;
for (int i = 2; i <= number; i++) { // Loop starts from i = 2
fibo = prev1 + prev2; // Calculation of next fibonacci number
prev2 = prev1;
prev1 = fibo;
}
return fibo;
}
The time complexity of this algorithm is O(n) where n is the value of the parameter passed to the function. This is the optimal time complexity for finding any fibonacci number since we have to go through all the numbers from 0 to n.
👩💻 can you write the full code with input to implement
Sure, here's the full code with input:
java Copy code
import java.util.Scanner;
public class Fibonacci {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the value of n to find the nth fibonacci number: ");
int n = scanner.nextInt();
int fibo = fibo(n);
System.out.println("The " + n + "th fibonacci number is: " + fibo);
}
public static int fibo(int number) {
if (number <= 1) { // Base cases for fibonacci series
return 1;
}
int prev1 = 1, prev2 = 1, fibo = 1;
for (int i = 2; i <= number; i++) { // Loop starts from i = 2
fibo = prev1 + prev2; // Calculation of next fibonacci number
prev2 = prev1;
prev1 = fibo;
}
return fibo;
}
}
This program takes the input from the user for the value of n and finds the nth fibonacci number using the fibo() function. Then it prints the result to the console.
👩💻 do you have any another better approach with optimal time complexity?
Yes, there is a better approach to find the nth Fibonacci number with an even better time complexity of O(log n). The idea is to use matrix exponentiation to compute the Fibonacci sequence.
Here is the code for the same:
java Copy code
public class Fibonacci {
private static long[][] multiply(long[][] A, long[][] B) {
int n1 = A.length, m1 = A[0].length;
int n2 = B.length, m2 = B[0].length;
assert m1 == n2;
long[][] C = new long[n1][m2];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < m2; j++) {
for (int k = 0; k < m1; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
private static long[][] matrixPower(long[][] A, long n) {
if (n == 1) return A;
long[][] B = matrixPower(A, n / 2);
B = multiply(B, B);
if (n % 2 != 0) {
B = multiply(B, A);
}
return B;
}
public static long fibonacci(long n) {
if (n == 0) return 0;
long[][] T = {{1, 1}, {1, 0}};
long[][] Tn = matrixPower(T, n);
return Tn[0][1];
}
public static void main(String[] args) {
long n = 50;
System.out.println("The " + n + "th Fibonacci number is: " + fibonacci(n));
}
}
In this approach, we use matrix exponentiation to find the nth Fibonacci number. We create a matrix T as:
T = {{1, 1}, {1, 0}}
Now we can find the nth Fibonacci number using matrix multiplication as:
T^n = {{F(n+1), F(n)}, {F(n), F(n-1)}}
Where F(i) is the ith Fibonacci number. So, the answer would be F(n) which is the element at position 0, 1 in T^n.
The multiply() method is used to multiply two matrices, and the matrixPower() method is used to compute the matrix power of T to get T^n.
👩💻 do you have any simple code with O(log n)?
Certainly, here's a simpler implementation of the same using recursion:
java Copy code
public class Fibonacci {
public static long fibonacci(long n) {
if (n == 0 || n == 1) return n;
if (n % 2 == 0) {
long k = n / 2;
long fk = fibonacci(k), fkm1 = fibonacci(k - 1);
return fk * (2 * fkm1 + fk);
} else {
long k = (n + 1) / 2;
long fk = fibonacci(k), fkm1 = fibonacci(k - 1);
return fk * fk + fkm1 * fkm1;
}
}
public static void main(String[] args) {
long n = 50;
System.out.println("The " + n + "th Fibonacci number is: " + fibonacci(n));
}
}
This approach recursively calculates the nth Fibonacci number in O(log n) time by exploiting the mathematical formula for computing Fibonacci numbers through recursion. We use the following formulae:
F(2k) = F(k) * (2*F(k-1) + F(k))
F(2k+1) = F(k+1)^2 + F(k)^2
Where F(k) is the kth Fibonacci number.
👩💻 Can you explain more detail in this code?
Sure, I'll explain the code in more detail.
The fibonacci() method takes an integer n as input and returns the nth Fibonacci number. This method uses recursion to calculate the Fibonacci number.
The first two base cases of the Fibonacci sequence (n = 0 and n = 1) are handled explicitly in the first line of the method, which returns n if n is 0 or 1.
The next step is to check whether n is even or odd. If n is even, we use the following recursive formula:
F(2k) = F(k) * (2*F(k-1) + F(k))
Where F(k) is the kth Fibonacci number. To calculate F(k) and F(k-1), we recursively call the fibonacci() method with k and k-1 respectively. We do this recursively until we reach the base cases where k = 0 or k = 1, which we already handled in the first line of the method. We then use these values of F(k) and F(k-1) to calculate F(2k) using the above formula.
If n is odd, we use the following recursive formula:
F(2k+1) = F(k+1)^2 + F(k)^2
Again, we recursively call the fibonacci() method with k+1 and k to calculate F(k+1) and F(k) respectively, until we reach the base cases where k+1 = 1 or k+1 = 0 and k = 1 or k = 0, which we again handled in the first line of the method. We then use these values of F(k+1) and F(k) to calculate F(2k+1) using the above formula.
Finally, we return the calculated Fibonacci number.
The time complexity of the fibonacci() method is O(log n) because the recursion tree has height log n. At each level of the recursion tree, we either reduce n by a factor of 2 (if n is even) or by a factor of 2 approximately (if n is odd). Therefore, the total number of nodes in the recursion tree is O(log n) and each node takes constant time to compute. So the overall time complexity is O(log n).
This is much faster than the time complexity of the iterative approach, which is O(n).
👩💻 Can you explain more about F(2k) = F(k) * (2*F(k-1) + F(k))
Certainly, I'll explain the formula F(2k) = F(k) * (2*F(k-1) + F(k)) in more detail.
This formula is used to calculate even-indexed Fibonacci numbers, where an even-indexed Fibonacci number is defined as the Fibonacci number at an index n that is divisible by 2 (i.e., n % 2 == 0).
For example, the 0th Fibonacci number is even, and can be calculated using the formula as follows:
F(2*0) = F(0) * (2*F(0-1) + F(0)) = 0 * (2*1 + 0) = 0
The 2nd Fibonacci number is also even, and can be calculated using the formula as follows:
F(2*1) = F(1) * (2*F(1-1) + F(1)) = 1 * (2*1 + 1) = 3
Note that we can also calculate odd-indexed Fibonacci numbers using the same formula, but it's more efficient to use a different formula for them (F(2k+1) = F(k+1)^2 + F(k)^2, which I explained in my previous message).
Now, let's try to understand how the formula F(2k) = F(k) * (2*F(k-1) + F(k)) works. Suppose we want to calculate F(2k) for some k. We can use the fact that the Fibonacci sequence satisfies the recurrence relation:
F(n) = F(n-1) + F(n-2)
If we substitute 2k for n in this formula, we get:
F(2k) = F(2k-1) + F(2k-2)
Now, we can use the fact that 2k-1 is odd and 2k-2 is even to simplify this formula. We can write:
F(2k) = F(k+1) * F(k+1) + F(k) * F(k)
This is the same formula we use to calculate odd-indexed Fibonacci numbers. However, this formula can also be rearranged into the form F(2k) = F(k) * (2*F(k-1) + F(k)), which is more efficient to compute using the recursive method. We can do this as follows:
F(2k) = F(k+1) * F(k+1) + F(k) * F(k)
F(2k) = F(k+1)^2 + F(k)^2
F(2k) = F(k) * (F(k+1) + F(k-1)) + F(k)^2
F(2k) = F(k) * (2*F(k-1) + F(k))
So, we use the formula F(2k) = F(k) * (2*F(k-1) + F(k)) instead of F(2k) = F(k+1)^2 + F(k)^2 to calculate even-indexed Fibonacci numbers when using the recursive method, as it's more efficient to compute.
👩💻 I still don't understand why from F(2k) = F(k+1)^2 + F(k)^2 we can swap to F(2k) = F(k) * (F(k+1) + F(k-1)) + F(k)^2
Good question! To derive this formula, we can use the following identities:
F(k+1) = F(k) + F(k-1) (from the recurrence relation of the Fibonacci sequence)F(k-1) = F(k+1) - F(k) (inverting the above identity)Now, we can substitute F(k+1) and F(k-1) in the formula F(2k) = F(k+1)^2 + F(k)^2 to get:
F(2k) = (F(k) + F(k-1))^2 + F(k)^2
Expanding this formula and simplifying it, we get:
F(2k) = F(k)^2 + 2 * F(k) * F(k-1) + F(k-1)^2 + F(k)^2
Rearranging the terms, we get:
F(2k) = F(k) * (F(k+1) + F(k-1)) + F(k)^2
This is the formula F(2k) = F(k) * (F(k+1) + F(k-1)) + F(k)^2 that we use to calculate even-indexed Fibonacci numbers.
👩💻 Expanding this formula and simplifying it, we get: F(2k) = F(k)^2 + 2 * F(k) * F(k-1) + F(k-1)^2 + F(k)^2 Rearranging the terms, we get: F(2k) = F(k) * (F(k+1) + F(k-1)) + F(k)^2 Can you explain how to rearrange?
Your request could not be processed by Athena because the convesation is too long. Please, ask Athena a new question instead.
function for fibonacci series , in python
In Python, you can create a function to generate a Fibonacci series:
python Copy code
# Function for nth Fibonacci number
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==1:
return 0
# Second Fibonacci number is 1
elif n==2:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2)
# Driver Program
print(Fibonacci(9))
If you have any other questions, you can easily reach out to us here
AI stands for Artificial Intelligence. AI bots are able to learn from conversations with users and expand their knowledge this way.
SheCodes Athena will help you with technical questions about your code using artificial intelligence to find the answer. Imagine a super powerful human who has memorized everything on the internet and can access that knowledge in a matter of seconds. 🤯
SheCodes Athena can answer most coding-related questions, even complicated ones! It can even find bugs in your code and tell you how to fix them in just a few seconds. Impressive, right?
Just remember we're still in testing mode so the AI may return strange or incorrect replies. Feel free to message us if this happens!
SheCodes Athena can only reply to coding-related technical questions. The same type of questions you would ask in the channels on Slack.
For questions that are not coding-related, write us here 😃
You should treat Athena like a SheCodes team member, so always be polite! 😊 Ask your questions as detailed as possible, just like you would do on Slack.
Here are some examples:
- Prettier isn't working on my VS Code. How do I fix this?
- How do I make bullet points with different colors using the list element?
- My code in Codesandbox is having some issues. Can you please tell me what the issue is? [Include the link to your Codesandbox]
For now, SheCodes Athena is limited to 5 questions per day for each student.
In that case, you can either ask SheCodes Athena a follow-up question, or you can post on the designated weekly channel on Slack!
Our technical assistants are still available on Slack and are always happy to help! 😍💪
Remember, questions are limited to 1000 characters.
- If you're working with an HTML file: Post a snippet of your code related to the issue you're having (just copy the code and paste it into the question box).
- If you're working with Codesandbox: Good news, you can just post the link to your Codesandbox and the AI Assistant will be able to view your code.
- If you have a longer question that would require an entire HTML file or more than 1000 characters, post it in the designated weekly channels on Slack! 😃
Athena was the Greek goddess of wisdom, among other elements. She received her name from the city of Athens, which she is known for protecting.
Much like the goddess Athena, SheCodes Athena is also incredibly wise and can solve complicated coding puzzles in a matter of seconds! 😍
Not likely. AI can automate tasks and make developers' jobs more efficient but it can't fully replace the human ability to deal with complex software. And AI will still require human developers to supervise and improve it further.
So developers may see their tasks change but they won't be replaced by AI. 👩💻🤝💻