Dada una array arr[] , la tarea es contar los pares en la array de modo que arr[i]/arr[j] sea una fracción pandigital .
Una fracción N/D se llama fracción pandigital si la fracción
contiene todos los dígitos del 0 al 9.
Ejemplos:
Entrada: arr = [ 12345, 67890, 123, 4567890 ]
Salida: 3
Explicación:
Las fracciones son 12345/67890, 12345/4567890 y 123/4567890Entrada: arr = [ 12345, 6789 ]
Salida: 0
Enfoque: la idea es iterar sobre cada par posible de la array usando dos bucles anidados y para cada par concatenar arr[i] y arr[j] en un solo número y verificar si la concatenación de arr[i] y arr[j ] es un número Pandigital en base 10 y luego incrementa el conteo.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 implementation of the
# above approach
import math
# Function to concatenate
# two numbers into one
def numConcat(num1, num2):
# Find number of digits in num2
digits = len(str(num2))
# Add zeroes to the end of num1
num1 = num1 * (10**digits)
# Add num2 to num1
num1 += num2
return num1
# Return true if n is pandigit
# else return false.
def checkPanDigital(n):
n = str(n)
b = 10
# Checking length is
# less than base
if (len(n) < b):
return 0;
hash = [0] * b;
# Traversing each digit
# of the number.
for i in range(len(n)):
# If digit is integer
if (n[i] >= '0' and \
n[i] <= '9'):
hash[ord(n[i]) - ord('0')] = 1;
# If digit is alphabet
elif (ord(n[i]) - ord('A') <= \
b - 11):
hash[ord(n[i]) - \
ord('A') + 10] = 1;
# Checking hash array, if any index is
# unmarked.
for i in range(b):
if (hash[i] == 0):
return 0;
return 1;
# Returns true if N is a
# Pandigital Fraction Number
def isPandigitalFraction(N, D):
join = numConcat(N, D)
return checkPanDigital(join)
# Returns number pandigital fractions
# in the array
def countPandigitalFraction(v, n) :
# iterate over all
# pair of strings
count = 0
for i in range(0, n) :
for j in range (i + 1,
n) :
if (isPandigitalFraction(v[i],
v[j])) :
count = count + 1
return count
# Driver Code
if __name__ == "__main__":
arr = [ 12345, 67890, 123, 4567890 ]
n = len(arr)
print(countPandigitalFraction(arr, n))
3
Complejidad de tiempo: O(N 2 )
Referencia: https://mathworld.wolfram.com/PandigitalFraction.html