Count of distinct N-digit odd integers that can be generated using given set of digits
Given an array arr[] of size N representing digits from 0 to 9, the task is to count the number of distinct odd N-digit integers that can be formed using the given digits in the array.
Examples:
Input: arr[] = {1, 0, 2, 4}
Output: 4
Explanation: The possible 4-digit odd integers that can be formed using the given digits are 2041, 2401, 4021 and 4201.Input: arr[] = {2, 3, 4, 1, 2, 3}
Output: 90
Approach: The given problem can be solved using the following observations:
- For the number to be odd, its unit place (i.e, 1st digit) should have an odd digit i.e., {1, 3, 5, 7, 9}
- Since the integer should have N digits, the most significant digit (digit at Nth place) can not be equal to 0.
- All the digits other than the digit at 1st and Nth place can have any other digit.
- The total number of ways to arrange X digits are X! / ( freq[0]! * freq[1]! *…* freq[9]! ), where freq[i] denotes the frequency of digit i in the given X digits.
In order to solve the problem keep track of the number of odd digits in a variable odd and the number of digits that are equal to 0 in a variable zero. So according to the above observations, if i represents the Nth digit and j represents the 1st digit, iterate over all possible values of i and j, and for each valid (i, j), calculate the number of ways of arranging the remaining (N-2) digits.
Below is the implementation of the above approach:
C++14
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of distinct // odd integers with N digits using the // given digits in the array arr[] int countOddIntegers( int arr[], int N) { // Stores the factorial of a number int Fact[N] = {}; // Calculate the factorial of all // numbers from 1 to N Fact[0] = 1; for ( int i = 1; i < N; i++) { Fact[i] = i * Fact[i - 1]; } // Stores the frequency of each digit int freq[10] = {}; for ( int i = 0; i < N; i++) { freq[arr[i]]++; } // Stores the final answer int ans = 0; // Loop to iterate over all values of // Nth digit i and 1st digit j for ( int i = 1; i <= 9; i += 2) { // If digit i does not exist in // the given array move to next i if (!freq[i]) continue ; // Fixing i as Nth digit freq[i]--; for ( int j = 1; j <= 9; j++) { // Stores the answer of a specific // value of i and j int cur_ans = 0; // If digit j does not exist // move to the next j if (freq[j] == 0) { continue ; } // Fixing j as 1st digit freq[j]--; // Calculate number of ways to // arrange remaining N-2 digits cur_ans = Fact[N - 2]; for ( int k = 0; k <= 9; k++) { cur_ans = cur_ans / Fact[freq[k]]; } ans += cur_ans; // Including j back into // the set of digits freq[j]++; } // Including i back into the // set of the digits freq[i]++; } // Return Answer return ans; } // Driver Code int main() { int A[] = { 2, 3, 4, 1, 2, 3 }; int N = sizeof (A) / sizeof ( int ); // Function Call cout << countOddIntegers(A, N); return 0; } |
Java
// Java program of the above approach import java.util.*; class GFG{ // Function to find the count of distinct // odd integers with N digits using the // given digits in the array arr[] static int countOddIntegers( int arr[], int N) { // Stores the factorial of a number int Fact[] = new int [N]; // Calculate the factorial of all // numbers from 1 to N Fact[ 0 ] = 1 ; for ( int i = 1 ; i < N; i++) { Fact[i] = i * Fact[i - 1 ]; } // Stores the frequency of each digit int freq[] = new int [ 10 ]; for ( int i = 0 ; i < N; i++) { freq[arr[i]]++; } // Stores the final answer int ans = 0 ; // Loop to iterate over all values of // Nth digit i and 1st digit j for ( int i = 1 ; i <= 9 ; i += 2 ) { // If digit i does not exist in // the given array move to next i if (freq[i] == 0 ) continue ; // Fixing i as Nth digit freq[i]--; for ( int j = 1 ; j <= 9 ; j++) { // Stores the answer of a specific // value of i and j int cur_ans = 0 ; // If digit j does not exist // move to the next j if (freq[j] == 0 ) { continue ; } // Fixing j as 1st digit freq[j]--; // Calculate number of ways to // arrange remaining N-2 digits cur_ans = Fact[N - 2 ]; for ( int k = 0 ; k <= 9 ; k++) { cur_ans = cur_ans / Fact[freq[k]]; } ans += cur_ans; // Including j back into // the set of digits freq[j]++; } // Including i back into the // set of the digits freq[i]++; } // Return Answer return ans; } // Driver Code public static void main(String[] args) { int A[] = { 2 , 3 , 4 , 1 , 2 , 3 }; int N = A.length; // Function Call System.out.print(countOddIntegers(A, N)); } } // This code is contributed by code_hunt |
Python3
# Python Program for the above approach from array import * from math import * # Function to find the count of distinct # odd integers with N digits using the # given digits in the array arr[] def countOddIntegers(arr, N): # Stores the factorial of a number # Calculate the factorial of all # numbers from 1 to N Fact = [ 0 ] * N Fact[ 0 ] = 1 for i in range ( 1 ,N): Fact[i] = i * Fact[i - 1 ] # Stores the frequency of each digit freq = [ 0 ] * 10 for i in range ( len (freq)): freq[i] = 0 ; for i in range (N): freq[arr[i]] = freq[arr[i]] + 1 ; # Stores the final answer ans = 0 # Loop to iterate over all values of # Nth digit i and 1st digit j for i in range ( 1 , 10 , 2 ) : # If digit i does not exist in # the given array move to next i if (freq[i] = = 0 ): continue # Fixing i as Nth digit freq[i] = freq[i] - 1 ; for j in range ( 1 , 10 , 1 ) : # Stores the answer of a specific # value of i and j cur_ans = 0 # If digit j does not exist # move to the next j if (freq[j] = = 0 ) : continue # Fixing j as 1st digit freq[j] = freq[j] - 1 ; # Calculate number of ways to # arrange remaining N-2 digits cur_ans = Fact[N - 2 ] for k in range ( 10 ): cur_ans = cur_ans / Fact[freq[k]] ans + = cur_ans # Including j back into # the set of digits freq[j] = freq[j] + 1 ; # Including i back into the # set of the digits freq[i] = freq[i] + 1 ; # Return Answer return ceil(ans) # Driver Code if __name__ = = "__main__" : A = [ 2 , 3 , 4 , 1 , 2 , 3 ] N = len (A) # Function Call print (countOddIntegers(A, N)) # This code is contributed by anudeep23042002. |
C#
// C# program of the above approach using System; class GFG{ // Function to find the count of distinct // odd integers with N digits using the // given digits in the array arr[] static int countOddIntegers( int []arr, int N) { // Stores the factorial of a number int []Fact = new int [N]; // Calculate the factorial of all // numbers from 1 to N Fact[0] = 1; for ( int i = 1; i < N; i++) { Fact[i] = i * Fact[i - 1]; } // Stores the frequency of each digit int []freq = new int [10]; for ( int i = 0; i < N; i++) { freq[arr[i]]++; } // Stores the final answer int ans = 0; // Loop to iterate over all values of // Nth digit i and 1st digit j for ( int i = 1; i <= 9; i += 2) { // If digit i does not exist in // the given array move to next i if (freq[i] == 0) continue ; // Fixing i as Nth digit freq[i]--; for ( int j = 1; j <= 9; j++) { // Stores the answer of a specific // value of i and j int cur_ans = 0; // If digit j does not exist // move to the next j if (freq[j] == 0) { continue ; } // Fixing j as 1st digit freq[j]--; // Calculate number of ways to // arrange remaining N-2 digits cur_ans = Fact[N - 2]; for ( int k = 0; k <= 9; k++) { cur_ans = cur_ans / Fact[freq[k]]; } ans += cur_ans; // Including j back into // the set of digits freq[j]++; } // Including i back into the // set of the digits freq[i]++; } // Return Answer return ans; } // Driver Code public static void Main(String[] args) { int []A = { 2, 3, 4, 1, 2, 3 }; int N = A.Length; // Function Call Console.Write(countOddIntegers(A, N)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the count of distinct // odd integers with N digits using the // given digits in the array arr[] function countOddIntegers(arr, N) { // Stores the factorial of a number let Fact = new Array(N); // Calculate the factorial of all // numbers from 1 to N Fact[0] = 1; for (let i = 1; i < N; i++) { Fact[i] = i * Fact[i - 1]; } // Stores the frequency of each digit let freq = new Array(10).fill(0); for (let i = 0; i < N; i++) { freq[arr[i]]++; } // Stores the final answer let ans = 0; // Loop to iterate over all values of // Nth digit i and 1st digit j for (let i = 1; i <= 9; i += 2) { // If digit i does not exist in // the given array move to next i if (!freq[i]) { continue ; } // Fixing i as Nth digit freq[i]--; for (let j = 1; j <= 9; j++) { // Stores the answer of a specific // value of i and j let cur_ans = 0; // If digit j does not exist // move to the next j if (freq[j] == 0) { continue ; } // Fixing j as 1st digit freq[j]--; // Calculate number of ways to // arrange remaining N-2 digits cur_ans = Fact[N - 2]; for (let k = 0; k <= 9; k++) { cur_ans = Math.floor(cur_ans / Fact[freq[k]]); } ans = ans + cur_ans; // Including j back into // the set of digits freq[j]++; } // Including i back into the // set of the digits freq[i]++; } // Return Answer return ans; } // Driver Code let A = [2, 3, 4, 1, 2, 3]; let N = A.length; // Function Call document.write(countOddIntegers(A, N)); // This code is contributed by Potta Lokesh </script> |
90
Time Complexity: O(N * 50)
Auxiliary Space: O(N) it is using extra space for array Fact