Número mínimo más cercano a N formado solo por dígitos impares

Dado un número entero N , la tarea es encontrar el número más cercano a N que tenga solo dígitos impares. Si existe más de uno de esos números, imprima el mínimo.

Ejemplos:

Entrada: N = 725
Salida: 719
Explicación:
Los números 719 y 731 consisten solo en dígitos impares y son los más cercanos a 725. Dado que 719 es el mínimo, es la respuesta requerida.

Entrada: N = 111
Salida : 111

Enfoque ingenuo : el enfoque más simple para resolver el problema es iterar y encontrar los números más cercanos menores y mayores que N, que solo tienen números impares como dígitos. Siga los pasos a continuación para resolver el problema:

Si todos los dígitos de N son impares, imprima N como respuesta.
Encuentre los números mayores y menores más cercanos y devuelva el que tenga la menor diferencia con N . Si se encuentra que ambos son equidistantes de N , imprima el número más pequeño.

Complejidad de tiempo : O(10 ^{(len(N) – 1)} )
Espacio auxiliar: O(1)

Enfoque eficiente : siga los pasos a continuación para optimizar el enfoque anterior:

Si todos los dígitos de N son impares, devuelva N .
Calcule el número más pequeño más cercano a N de manera eficiente mediante los siguientes pasos:
- Encuentre la posición del primer dígito par en N de izquierda a derecha, es decir, pos .
- Si el primer dígito par es 0 , reemplace 0 con 9 e itere sobre todos los dígitos anteriores y para cada dígito, si se encuentra que es 1 , reemplácelo con 9 . De lo contrario, disminuya el dígito en 2 y devuelva el número.
- Si no se encuentra que los dígitos anteriores excedan 1 , reemplace el dígito más significativo con 0 .
- Si el primer dígito par no es cero, disminuya ese dígito en 1. Reemplace todos los dígitos siguientes con 9 .
Calcula el mayor número más cercano a N siguiendo los pasos a continuación:
- Encuentre la posición del primer dígito par, es decir , pos .
- Incremente los dígitos en pos en 1.
- Iterar sobre los dígitos siguientes e incrementarlos en 1.
Compare la diferencia absoluta de los respectivos números más cercanos obtenidos con N e imprima el que tenga menor diferencia.
Si se encuentra que ambas diferencias son iguales, imprima el número más pequeño.

A continuación se muestra la implementación del enfoque anterior:

Python

# Python program to implement
# the above approach
  
# Function to return the smaller
# number closest to N made up of
# only odd digits
def closest_smaller(N):
  
    N = str(N)
  
    l = list(map(int, N))
    length = len(l)
      
    # Stores the position of
    # first even digit of N
    pos = -1
  
    # Iterate through each digit of N
    for i in range(length):
          
        # Check for even digit.
        if l[i] % 2 == 0:
            pos = i
            break
  
    # If the first even digit is 0
    if l[pos] == 0:
  
        # Replace 0 with 9
        l[pos] = 9
  
        # Iterate over preceding
        # digits
        for i in range(pos - 1, -1, -1):
  
            # If current digit is 1
            if l[i] == 1:
  
                # Check if it is the 
                # first digit or not
                if i == 0:
                      
                    # Append leading 0's
                    l[i] = 0
                    break
                      
                # Otherwise, replace by 9
                l[i] = 9
                  
            # Otherwise
            else:
  
                # Decrease its value by 2
                l[i] -= 2
                break
  
    # If the first even digit exceeds 0
    else:
          
        # Reduce the digit by 1
        l[pos] -= 1
  
    # Replace all succeeding digits by 9
    for i in range(pos + 1, length):
        l[i] = 9
  
    # Remove leading 0s
    if l[0] == 0:
        l.pop(0)
      
      
    result = ''.join(map(str, l))
    return result
      
# Function to return the greater
# number closest to N made up of
# only odd digits
def closest_greater(N):
  
    N = str(N)
  
    l = list(map(int, N))
    length = len(l)
  
    # Stores the position of
    # first even digit of N
    pos = -1
  
    # Iterate over each digit
    # of N
    for i in range(length):
          
        # If even digit is found
        if l[i] % 2 == 0:
            pos = i
            break
              
    # Increase value of first 
    # even digit by 1
    l[pos] += 1
  
    for i in range(pos + 1, length):
        l[i] = 1
  
    result = ''.join(map(str, l))
    return result
  
# Function to check if all 
# digits of N are odd or not
def check_all_digits_odd(N):
  
    N = str(N)
  
    l = list(map(int, N))
    length = len(l)
  
    # Stores the position of
    # first even digit of N
    pos = -1
  
    # Iterating over each digit
    # of N
    for i in range(length):
          
        # If even digit is found
        if l[i] % 2 == 0:
            pos = i
            break
              
    # If no even digit is found
    if pos == -1:
        return True
    return False
  
# Function to return the 
# closest number to N
# having odd digits only
def closestNumber(N):
      
    # If all digits of N are odd
    if check_all_digits_odd(N):
        print(N)
    else:
          
        # Find smaller number 
        # closest to N
        l = int(closest_smaller(N))
          
        # Find greater number 
        # closest to N
        r = int(closest_greater(N))
          
        # Print the number with least
        # absolute difference
        if abs(N - l) <= abs(N - r):
            print(l)
        else:
            print(r)
  
# Driver Code.
if __name__ == '__main__':
      
    N = 110
    closestNumber(N)

Producción:

Complejidad de tiempo: O(len(N))
Espacio auxiliar: O(len(N))

Publicación traducida automáticamente

Artículo escrito por aditya_panwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Python

Deja una respuesta Cancelar la respuesta