Número mínimo posible con la operación dada

Dado un entero positivo N , la tarea es convertir este entero al mínimo entero posible sin ceros a la izquierda cambiando los dígitos. Un dígito X solo se puede cambiar a un dígito Y si X + Y = 9 .
Ejemplos: 
 

Entrada: N = 589 
Salida: 410 
Cambiar 5 -> 4, 8 -> 1 y 9 -> 0
Entrada: N = 934 
Salida: 934 
934 no se puede minimizar. 
 

Enfoque: solo se deben cambiar los dígitos que son mayores o iguales a 5 , ya que cambiar los dígitos que son menores a 5 dará como resultado un número mayor. Después de que se hayan actualizado todos los dígitos requeridos, verifique si el número resultante tiene un cero inicial, si es así, cámbielo a un 9 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum possible
// integer that can be obtained from the
// given integer after performing
// the given operations
string minInt(string str)
{
    // For every digit
    for (int i = 0; i < str.length(); i++) {
 
        // Digits less than 5 need not to be
        // changed as changing them will
        // lead to a larger number
        if (str[i] >= '5') {
            str[i] = ('9' - str[i]) + '0';
        }
    }
 
    // The resulting integer
    // cannot have leading zero
    if (str[0] == '0')
        str[0] = '9';
 
    return str;
}
 
// Driver code
int main()
{
    string str = "589";
 
    cout << minInt(str);
 
    return 0;
}

// Java implementation of the approach
 
// Function to return the minimum possible
// integer that can be obtained from the
// given integer after performing
// the given operations
 
import java.util.*;
 
class GFG{
 
static String minInt(String str)
{
    // For every digit
    String s = "";
    for (int i = 0; i < str.length(); i++)
    {
 
        // Digits less than 5 need not to be
        // changed as changing them will
        // lead to a larger number
        if (str.charAt(i) >= '5')
        {
            s += (char)(('9' - str.charAt(i)) + '0');
        }
        else
        {
            s += str.charAt(i);
        }
         
    }
 
    // The resulting integer
    // cannot have leading zero
    if (str.charAt(0) == '0')
        s += '9';
 
    return s;
}
 
// Driver code
public static void main(String []args)
{
    String str = "589";
 
    System.out.println(minInt(str));
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 implementation of the approach
  
# Function to return the minimum possible
# integer that can be obtained from the
# given integer after performing
# the given operations
def minInt(str1):
     
    # For every digit
    for i in range(len(str1)):
 
        # Digits less than 5 need not to be
        # changed as changing them will
        # lead to a larger number
        if (str1[i] >= 5):
            str1[i] = (9 - str1[i])
 
    # The resulting integer
    # cannot have leading zero
    if (str1[0] == 0):
        str1[0] = 9
         
    temp = ""
 
    for i in str1:
        temp += str(i)
 
    return temp
 
# Driver code
str1 = "589"
str1 = [int(i) for i in str1]
 
print(minInt(str1))
 
# This code is contributed by Mohit Kumar

// C# implementation of the above approach
using System;
 
class GFG
{
     
    // Function to return the minimum possible
    // integer that can be obtained from the
    // given integer after performing
    // the given operations
    static string minInt(char []str)
    {
        // For every digit
        for (int i = 0; i < str.Length; i++)
        {
     
            // Digits less than 5 need not to be
            // changed as changing them will
            // lead to a larger number
            if ((int)str[i] >= (int)('5'))
            {
                str[i] = (char)(((int)('9') -
                                 (int)(str[i])) +
                                 (int)('0'));
            }
        }
     
        // The resulting integer
        // cannot have leading zero
        if (str[0] == '0')
            str[0] = '9';
     
        string s = new string(str);
        return s;
    }
     
    // Driver code
    static public void Main ()
    {
        string str = "589";
        Console.WriteLine(minInt(str.ToCharArray()));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
    // JavaScript implementation of the above approach
     
    // Function to return the minimum possible
    // integer that can be obtained from the
    // given integer after performing
    // the given operations
    function minInt(str)
    {
        // For every digit
        for (let i = 0; i < str.length; i++)
        {
       
            // Digits less than 5 need not to be
            // changed as changing them will
            // lead to a larger number
            if (str[i].charCodeAt() >= ('5').charCodeAt())
            {
                str[i] = String.fromCharCode((('9').charCodeAt() -
                                 (str[i]).charCodeAt()) +
                                 ('0').charCodeAt());
            }
        }
       
        // The resulting integer
        // cannot have leading zero
        if (str[0] == '0')
            str[0] = '9';
       
        let s = str.join("");
        return s;
    }
     
    let str = "589";
      document.write(minInt(str.split('')));
             
</script>

410

Complejidad de tiempo: O(|str|)

Espacio Auxiliar: O(1)