Dada una array arr[] de tamaño N que representa los dígitos del 0 al 9 , la tarea es contar el número de enteros de N dígitos impares distintos que se pueden formar usando los dígitos dados en la array.
Ejemplos:
Entrada: arr[] = {1, 0, 2, 4}
Salida: 4
Explicación: Los posibles enteros impares de 4 dígitos que se pueden formar usando los dígitos dados son 2041, 2401, 4021 y 4201.Entrada: arr[] = {2, 3, 4, 1, 2, 3}
Salida: 90
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- Para que el número sea impar, su lugar de unidad (es decir, el 1er dígito) debe tener un dígito impar, es decir, {1, 3, 5, 7, 9}
- Dado que el número entero debe tener N dígitos, el dígito más significativo (el dígito en el lugar N ) no puede ser igual a 0 .
- Todos los dígitos que no sean el dígito en el lugar 1 y N pueden tener cualquier otro dígito.
- ¡ El número total de formas de ordenar X dígitos es X! / ( freq[0]! * freq[1]! *…* freq[9]! ) , donde freq[i] denota la frecuencia del dígito i en los X dígitos dados.
Para resolver el problema, lleve la cuenta del número de dígitos impares en una variable impar y el número de dígitos que son iguales a 0 en una variable cero . Entonces, de acuerdo con las observaciones anteriores, si i representa el dígito N y j representa el dígito 1 , itere sobre todos los valores posibles de i y j , y para cada (i, j) válido , calcule el número de formas de organizar el dígitos restantes (N-2) .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
90
Complejidad de Tiempo: O(N * 50)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohanhstory5a6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA