# Count N-digits numbers made up of even and prime digits at odd and even positions respectively

Given a positive integer **N**, the task is to find the number of integers of **N digits** having even digits at odd indices and prime digits at even indices.

**Examples:**

Input:N = 2Output:20Explanation:

Following are the possible number of 2-digits satisfying the given criteria {20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 50, 52, 54, 56, 58, 70, 72, 74, 76, 78}. Therefore, the count of such number is 20.

Input:N = 5Output:1600

**Approach:** The given problem can be solved using the concept of **Permutations and Combinations** by observing the fact that there are only** 4** choices for the **even positions** as **[2, 3, 5, 7] **and **5 **choices for the **odd positions** as **[0, 2, 4, 6, 8]**. Therefore, the count of N-digits numbers satisfying the given criteria is given by:

total count = 4

^{P}5^{Q}, where P and Q is the number of even and odd positions respectively.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approache` `#include<bits/stdc++.h>` `using` `namespace` `std;` `int` `m = 1000000007;` `// Function to find the value of x ^ y` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` ` ` `// Stores the value of x ^ y` ` ` `int` `res = 1;` ` ` `// Iterate until y is positive` ` ` `while` `(y > 0)` ` ` `{` ` ` ` ` `// If y is odd` ` ` `if` `((y & 1) != 0)` ` ` `res = (res * x) % m;` ` ` `// Divide y by 2` ` ` `y = y >> 1;` ` ` `x = (x * x) % m;` ` ` `}` ` ` ` ` `// Return the value of x ^ y` ` ` `return` `res;` `}` `// Function to find the number of N-digit` `// integers satisfying the given criteria` `int` `countNDigitNumber(` `int` `N)` `{` ` ` ` ` `// Count of even positions` ` ` `int` `ne = N / 2 + N % 2;` ` ` `// Count of odd positions` ` ` `int` `no = ` `floor` `(N / 2);` ` ` `// Return the resultant count` ` ` `return` `power(4, ne) * power(5, no);` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5;` ` ` `cout << countNDigitNumber(N) % m << endl;` `}` `// This code is contributed by SURENDRA_GANGWAR` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` `static` `int` `m = ` `1000000007` `;` `// Function to find the value of x ^ y` `static` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` ` ` `// Stores the value of x ^ y` ` ` `int` `res = ` `1` `;` ` ` `// Iterate until y is positive` ` ` `while` `(y > ` `0` `)` ` ` `{` ` ` ` ` `// If y is odd` ` ` `if` `((y & ` `1` `) != ` `0` `)` ` ` `res = (res * x) % m;` ` ` `// Divide y by 2` ` ` `y = y >> ` `1` `;` ` ` `x = (x * x) % m;` ` ` `}` ` ` ` ` `// Return the value of x ^ y` ` ` `return` `res;` `}` `// Function to find the number of N-digit` `// integers satisfying the given criteria` `static` `int` `countNDigitNumber(` `int` `N)` `{` ` ` ` ` `// Count of even positions` ` ` `int` `ne = N / ` `2` `+ N % ` `2` `;` ` ` `// Count of odd positions` ` ` `int` `no = (` `int` `)Math.floor(N / ` `2` `);` ` ` `// Return the resultant count` ` ` `return` `power(` `4` `, ne) * power(` `5` `, no);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `5` `;` ` ` `System.out.println(countNDigitNumber(N) % m);` `}` `}` `// This code is contributed by sanjoy_62.` |

## Python3

`# Python program for the above approach` `import` `math` `m ` `=` `10` `*` `*` `9` `+` `7` `# Function to find the value of x ^ y` `def` `power(x, y):` ` ` ` ` `# Stores the value of x ^ y` ` ` `res ` `=` `1` ` ` ` ` `# Iterate until y is positive` ` ` `while` `y > ` `0` `:` ` ` ` ` `# If y is odd` ` ` `if` `(y & ` `1` `) !` `=` `0` `:` ` ` `res ` `=` `(res ` `*` `x) ` `%` `m` ` ` ` ` `# Divide y by 2` ` ` `y ` `=` `y >> ` `1` ` ` ` ` `x ` `=` `(x ` `*` `x) ` `%` `m` ` ` ` ` `# Return the value of x ^ y` ` ` `return` `res` `# Function to find the number of N-digit` `# integers satisfying the given criteria` `def` `countNDigitNumber(n: ` `int` `) ` `-` `> ` `None` `:` ` ` ` ` `# Count of even positions` ` ` `ne ` `=` `N ` `/` `/` `2` `+` `N ` `%` `2` ` ` ` ` `# Count of odd positions` ` ` `no ` `=` `N ` `/` `/` `2` ` ` ` ` `# Return the resultant count` ` ` `return` `power(` `4` `, ne) ` `*` `power(` `5` `, no)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `N ` `=` `5` ` ` `print` `(countNDigitNumber(N) ` `%` `m)` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `static` `int` `m = 1000000007;` `// Function to find the value of x ^ y` `static` `int` `power(` `int` `x, ` `int` `y)` `{` ` ` ` ` `// Stores the value of x ^ y` ` ` `int` `res = 1;` ` ` `// Iterate until y is positive` ` ` `while` `(y > 0)` ` ` `{` ` ` ` ` `// If y is odd` ` ` `if` `((y & 1) != 0)` ` ` `res = (res * x) % m;` ` ` `// Divide y by 2` ` ` `y = y >> 1;` ` ` `x = (x * x) % m;` ` ` `}` ` ` ` ` `// Return the value of x ^ y` ` ` `return` `res;` `}` `// Function to find the number of N-digit` `// integers satisfying the given criteria` `static` `int` `countNDigitNumber(` `int` `N)` `{` ` ` ` ` `// Count of even positions` ` ` `int` `ne = N / 2 + N % 2;` ` ` `// Count of odd positions` ` ` `int` `no = (` `int` `)Math.Floor((` `double` `)N / 2);` ` ` `// Return the resultant count` ` ` `return` `power(4, ne) * power(5, no);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 5;` ` ` `Console.Write(countNDigitNumber(N) % m);` `}` `}` `// This code is contributed by splevel62.` |

## Javascript

` ` `<script>` ` ` `// JavaScript program for the above approache` ` ` `var` `m = 10 ** 9 + 7` ` ` `// Function to find the value of x ^ y` ` ` `function` `power(x, y) {` ` ` `// Stores the value of x ^ y` ` ` `var` `res = 1` ` ` `// Iterate until y is positive` ` ` `while` `(y > 0) {` ` ` `// If y is odd` ` ` `if` `((y & 1) != 0)` ` ` `res = (res * x) % m` ` ` `// Divide y by 2` ` ` `y = y >> 1` ` ` `x = (x * x) % m` ` ` `}` ` ` `// Return the value of x ^ y` ` ` `return` `res` ` ` `}` ` ` `// Function to find the number of N-digit` ` ` `// integers satisfying the given criteria` ` ` `function` `countNDigitNumber(N) {` ` ` `// Count of even positions` ` ` `var` `ne = Math.floor(N / 2) + N % 2` ` ` `// Count of odd positions` ` ` `var` `no = Math.floor(N / 2)` ` ` `// Return the resultant count` ` ` `return` `power(4, ne) * power(5, no)` ` ` `}` ` ` `// Driver Code` ` ` `let N = 5` ` ` `document.write(countNDigitNumber(N) % m);` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

1600

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**