EASY

Math,Arrays.

# PROBLEM:

As the COVID-19 Pandemic is on it’s Peak in India. The total number of Covid cases are increasing day by day. The Following series shows the number of cases on a particular day.

1,2,3,5,8,13,21,34,55,89,144,….

On the 1st Day the total cases where 1, on second day total cases where 2 , on third day 3 and so on.

You have to write a program which will calculate the total number of cases on the Nth day. According to the above series.

# QUICK EXPLANATION:

You have to just add the last two values of array to form the current index value.

# EXPLANATION:

Let’s understand the pattern with example
1,2,3,5,8,13,21,34,55,89,144,….

if you observe the above pattern for some time then you will find that the every 3rd index value is the addition of last two index values.
i.e a[4]=8 is the addition of its last two indexes a[4-1]+a[4-2]=5+3.

lastly you have to print the a[n-1] as stated in the question a[n-1] will be the total number of cases on the nth day.
you have to do this N times as stated in the question.

As the constraints are very small you can do this question in any complexity.

# SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int temp;
long long int arr[94];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
for(int i=3;i<94;i++)
{
arr[i] = arr[i-1] + arr[i-2];
}

  cout<<arr[n-1]<<endl;


}
return 0;
}

Tester's Solution

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int temp;
long long int arr[94];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
for(int i=3;i<94;i++)
{
arr[i] = arr[i-1] + arr[i-2];
}

  cout<<arr[n-1]<<endl;


}
return 0;
}

Editorialist's Solution

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int temp;
long long int arr[94];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
for(int i=3;i<94;i++)
{
arr[i] = arr[i-1] + arr[i-2];
}

  cout<<arr[n-1]<<endl;


}
return 0;
}

1 Like

Bonus: Can you solve this in O(\log{N})?
Given that N can be as large as 10^9 and you have to find the result modulo 10^9+7.

2 Likes

I think using binet’s formula it could be solved in O(log n) time.

1 Like

But that’s just an approximation. It doesn’t work for large values of N.

1 Like

can you plzz connect me on linkedin we will talk there

can you plzz elaborate how?

Done

Okay. How are we going to do it in O(\log{N})?
One of the Identities of Fibonacci Numbers is:

\sum_{i = 1}^{n} F_i = F_{n + 2} - 1

where F_i is i^{th} Fibonacci Number.

Source: Combinatorial Identities
(See the section under Combinatorial Identities)

Now, our problem reduces to finding (N+2)^{th} Fibonacci Number. Using Matrix Exponentiation, we can find N^{th} Fibonacci Number in O(\log{N}) time.

Source: Matrix Form
(See the section under Matrix Form)

Basically, \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {N} = \begin{bmatrix} F_{N+1} & F_{N} \\ F_{N} & F_{N - 1} \end{bmatrix}.

The N^{th} power of matrix can be calculated in O(16 \times \log{N}) where 16 signifies the number of steps involved in Matrix Multiplication and \log{N} signifies the number of steps involved in Exponentiation.

Feel free to assert if there are any mistakes.

Edit: I actually misread the question as
Given the number of new cases everyday, find the total number of cases at the end of N^{th} day.

However, the approach remains the same. Instead of (N+2)^{th} Fibonacci Number, we’ll find N^{th} Fibonacci Number in \log{N} time.

1 Like