1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Count of numbers of length N having odd numbers at even indices and prime numbers at odd indices

## 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.

Q1.What data type does the POW function return?

Answer: The pow() function returns the base to the exponent power, as in base^exponent, the base and the exponent are in the decimal numeral system. Because pow() is a static method of Math, use it as Math.

Q2. Is there any formula to check whether a number is prime or not?

Answer: The numbers 2 and 3 are two consecutive natural and prime numbers. Except for the numbers 2 and 3, every prime number can be written as 6n + 1 or 6n – 1, where n is a natural number.

Q3. How to find that a number N is prime or not?

Answer: Run a loop from 1 to N and count all the divisors of N. if the count of divisors is 2 (1 and the number itself), it is a prime number. Else it is not a prime number.

Q4. Is zero prime or composite?

Answer: Zero is neither composite nor prime. Because any number multiplied by zero equals zero, a product of zero has an infinite number of factors. There must be a finite number of factors in a composite number. One is also neither composite nor prime.

Q5. What is the smallest, even prime number?

Answer: A prime number is defined as a number that can only be divided by one and itself. Because numbers divided by zero are undefined, a prime number cannot be divided by zero. The smallest prime number is 2, which is also the only prime number that is even.

## Key Takeaways

This article discussed the approach to counting the numbers of length N having prime numbers at odd indices and odd numbers at even indices with examples for a better understanding and implementation in C++.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!