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 = 2
Output: 20
Explanation:
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 = 5
Output: 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 = 4P5Q, where P and Q is the number of even and odd positions respectively.
Efficient Approach:
- Define a variable m with value 1000000007.
- Define a function named “power” which will accept two integer parameters named “x” and “y“. This function will return the value of x^y.
Inside the function power, initialize a variable res with value 1.- Run a loop until y is greater than 0. Inside the loop:
a. If the last bit of y is 1 (i.e., if y is odd), then multiply res with x and take modulo with m.
b. Divide y by 2.
c. Multiply x by x and take modulo with m. - Return the value of res.
- Run a loop until y is greater than 0. Inside the loop:
- Define another function named “countNDigitNumber” which will accept an integer parameter named “N“. This function will return the number of N-digit integers satisfying the given criteria.
- Inside the function countNDigitNumber, define two integer variables named “ne” and “no“. ne will hold the count of even positions and no will hold the count of odd positions. Initialize ne with N/2 + N%2 and no with floor(N/2).
- Return the product of power(4, ne) and power(5, no) modulo m.
- Inside the main function:
a. Define an integer variable N and initialize it with 5.
b. Call the function countNDigitNumber with parameter N and print the result modulo m.
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 ^ yint 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 criteriaint 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 Codeint main(){ int N = 5; cout << countNDigitNumber(N) % m << endl;}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.io.*;class GFG {static int m = 1000000007;// Function to find the value of x ^ ystatic 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 criteriastatic 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 Codepublic 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 approachimport mathm = 10**9 + 7# Function to find the value of x ^ ydef 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 criteriadef 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 Codeif __name__ == '__main__': N = 5 print(countNDigitNumber(N) % m) |
C#
// C# program for the above approachusing System;class GFG{static int m = 1000000007;// Function to find the value of x ^ ystatic 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 criteriastatic 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 Codepublic 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)
Dynamic Approach:
- Define a function “isPrime” that takes an integer “num” as input and checks if it is prime. It returns “true” if the number is prime and “false” otherwise.
- Define a function “countIntegers” that takes an integer “N” as input and returns the count of integers satisfying the given criteria.
- Create a 2D vector “dp” of size (N+1) x 2 to store the intermediate results. Each element “dp[i][j]” represents the count of integers with “i” digits, where “j=0” indicates even digits at odd indices, and “j=1” indicates prime digits at even indices.
- Initialize the base cases: “dp[1][0] = 5” and “dp[1][1] = 4” since there are 5 even digits (0, 2, 4, 6, 8) and 4 prime digits (2, 3, 5, 7) for a single-digit number.
- Iterate from “i = 2” to “N”:
Calculate the count of even digits at odd indices for “i” digits: “dp[i][0] = 5 * dp[i – 1][1]”.
Calculate the count of prime digits at even indices for “i” digits: “dp[i][1] = 4 * dp[i – 1][0]”. - Return the total count of valid integers: “dp[N][1].
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;// Function to check if a number is primebool isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true;}// Function to count the number of integersint countIntegers(int N) { vector<vector<int>> dp(N + 1, vector<int>(2)); // Initialize the base cases dp[1][0] = 5; // Even digits at odd indices dp[1][1] = 4; // Prime digits at even indices for (int i = 2; i <= N; i++) { // Calculate the count of even digits at odd indices dp[i][0] = 5 * dp[i - 1][1]; // Calculate the count of prime digits at even indices dp[i][1] = 4 * dp[i - 1][0]; } // Return the total count of valid integers return dp[N][1];}int main() { int N = 5; int count = countIntegers(N); cout << count <<endl; return 0;}// This code is contributed by rudra1807raj |
Java
import java.util.*;class Main { // Function to check if a number is prime static boolean isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } // Function to count the number of integers static int countIntegers(int N) { int[][] dp = new int[N + 1][2]; // Initialize the base cases dp[1][0] = 5; // Even digits at odd indices dp[1][1] = 4; // Prime digits at even indices for (int i = 2; i <= N; i++) { // Calculate the count of even digits at odd indices dp[i][0] = 5 * dp[i - 1][1]; // Calculate the count of prime digits at even indices dp[i][1] = 4 * dp[i - 1][0]; } // Return the total count of valid integers return dp[N][1]; } public static void main(String[] args) { int N = 5; int count = countIntegers(N); System.out.println(count); // This Code Is Contributed By Shubham Tiwari. }} |
Python3
def isPrime(num): if num <= 1: return False for i in range(2, int(num**0.5) + 1): if num % i == 0: return False return Truedef countIntegers(N): dp = [[0 for _ in range(2)] for _ in range(N + 1)] # Initialize the base cases dp[1][0] = 5 # Even digits at odd indices dp[1][1] = 4 # Prime digits at even indices for i in range(2, N + 1): # Calculate the count of even digits at odd indices dp[i][0] = 5 * dp[i - 1][1] # Calculate the count of prime digits at even indices dp[i][1] = 4 * dp[i - 1][0] # Return the total count of valid integers return dp[N][1]if __name__ == "__main__": N = 5 count = countIntegers(N) print(count)# This Code Is Contributed By Shubham Tiwari |
C#
using System;using System.Collections.Generic;class Program { // Function to check if a number is prime static bool IsPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } // Function to count the number of integers static int CountIntegers(int N) { int[][] dp = new int[N + 1][]; for (int i = 0; i <= N; i++) { dp[i] = new int[2]; } // Initialize the base cases dp[1][0] = 5; // Even digits at odd indices dp[1][1] = 4; // Prime digits at even indices for (int i = 2; i <= N; i++) { // Calculate the count of even digits at odd indices dp[i][0] = 5 * dp[i - 1][1]; // Calculate the count of prime digits at even indices dp[i][1] = 4 * dp[i - 1][0]; } // Return the total count of valid integers return dp[N][1]; } static void Main() { int N = 5; int count = CountIntegers(N); Console.WriteLine(count); // This Code Is Contributed By Shubham Tiwari }} |
Javascript
// Function to check if a number is primefunction isPrime(num) { if (num <= 1) return false; for (let i = 2; i * i <= num; i++) { if (num % i === 0) return false; } return true;}// Function to count the number of integersfunction countIntegers(N) { let dp = Array(N + 1).fill().map(() => Array(2).fill(0)); // Initialize the base cases dp[1][0] = 5; // Even digits at odd indices dp[1][1] = 4; // Prime digits at even indices for (let i = 2; i <= N; i++) { // Calculate the count of even digits at odd indices dp[i][0] = 5 * dp[i - 1][1]; // Calculate the count of prime digits at even indices dp[i][1] = 4 * dp[i - 1][0]; } // Return the total count of valid integers return dp[N][1];}let N = 5;let count = countIntegers(N);console.log(count);//This Code Is Contributed By Shubham Tiwari |
Output
1600
Time Complexity: O(N).
Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
