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: 100Also 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.
38+ registered 