## Introduction

### Problem statement

We are given a number N. Our task is to count the numbers of length N having odd numbers at even indices and prime numbers at odd indices.

Here, consider the indexing as 0-based and consider 0 as an even number.

### Sample Examples

**Example 1:**

```
Input: N = 1
Output: 5
Explanation
For length = 1, there is only 1 even index, valid numbers are: { 1, 3, 5, 7, 9 }
```

**Example 2:**

```
Input: N= 3
Output: 100
```

Also see, __Euclid GCD Algorithm__

## Approach

We need to fill the prime numbers at odd indices and odd numbers at even indices in this problem.

Valid numbers for odd indices = { 2, 3, 5, 7}, and valid numbers for even indices ={ 1, 3, 5, 7, 9}.

So, there are 4 choices for the odd indices and 5 choices of numbers for the even indices.

Here we assume the first index is 0 and an even index. So, the total number of odd indices = N/2 and the total number of even indices = (N/2) + (N%2).

Now, we have 4 valid choices for every odd index. The total number of ways to fill the odd index = 4 ^ number of odd indexes. Similarly, we have 5 valid choices for every even index. The total number of ways to fill the even index = 5 ^ number of even indexes.

The total number of ways to fill all indexes = The number of ways to fill even indexes * The number of ways to fill odd indexes.

### Steps of algorithm

- First, we count the even and odd indices, indices_even = (N/2)+(N%2) and indices_odd = N/2.
- There are 4 choices for every single odd index, so the number of ways to fill the prime numbers at odd indices, ways_odd = 4 ^ indices_odd.
- Similarly, there are 5 choices for every single even index, so the number of ways to fill the odd numbers at even indices, ways_even = 5 ^ indices_even.
- Total count of valid numbers = ways_odd * ways_even.

Let’s understand the above approach with an example:

Given number = 3.

Even indexes = 2, odd indexes = 1.

Valid numbers to fill the odd indexes are = { 2, 3, 5, 7 } = 4.

Valid numbers to fill the even indexes are = { 1, 3, 5, 7, 9 } = 5.

Ways to fill odd indexes = 4 ^ 1 = 4.

Ways to fill the even indexes = 5 ^ 2= 25.

Total valid numbers = 25 * 4 = 100.

### Implementation in C++

```
#include<bits/stdc++.h>
using namespace std;
int total_ways(int n)
{
int indices_odd = n / 2;
int indices_even = (n / 2) + (n % 2);
int ways_odd = pow(4, indices_odd);
int ways_even = pow(5, indices_even);
return ways_odd * ways_even;
}
int main()
{
int n = 3;
cout << total_ways(n) << endl;
return 0;
}
```

**Output:**

`100`

#### Complexity Analysis

**Time complexity:** O(1), as we are using the pow function.

**Space complexity:** O(1), as we are using constant extra space.