Encuentre el número más pequeño formado al invertir los dígitos del número dado N

Dado un número entero N , la tarea es formar un número positivo mínimo posible (>0) invirtiendo algunos dígitos de N .

Invertir para un dígito T se define como restarlo de 9 que es 9 – T.

Nota: El número final no debe comenzar desde cero.

Ejemplos:

Entrada: N = 4545
Salida: 4444
Explicación:
El número mínimo posible es 4444 restando los dos 5 ( 9 – 5 = 4)

Entrada: N = 9000
Salida: 9000
Explicación:
El número mínimo posible es 9000 porque el número tiene que ser > 0 y, por lo tanto, 9 no se puede restar de sí mismo.

 

Enfoque: La idea es iterar sobre todos los dígitos en el número dado y verificar si 9 – dígito_actual es menor que el dígito_actual y luego reemplazar ese dígito con 9 – dígito_actual; de lo contrario, no cambie el dígito. Si el primer dígito del número es 9 , no cambie el dígito y no podemos tener un cero final en el nuevo número formado.

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

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to invert the digits of
// integer N to form minimum
// possible number
void number(int num)
{
    // Initialize the array
    int a[20], r, i = 0, j;
 
    // Iterate till the number N exists
    while (num > 0) {
 
        // Last digit of the number N
        r = num % 10;
 
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
 
            // Store the smaller
            // digit in the array
            a[i] = r;
 
        else
            a[i] = 9 - r;
 
        i++;
 
        // Reduce the number each time
        num = num / 10;
    }
 
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0) {
        cout << 9;
        i--;
    }
 
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        cout << a[j];
}
 
// Driver Code
int main()
{
    // Given Number
    long long int num = 4545;
 
    // Function Call
    number(num);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
  
// Function to invert the digits of
// integer N to form minimum
// possible number
static void number(int num)
{
    // Initialize the array
    int a[] = new int[20];
    int r, i = 0, j;
  
    // Iterate till the number N exists
    while (num > 0)
    {
  
        // Last digit of the number N
        r = num % 10;
  
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
  
            // Store the smaller
            // digit in the array
            a[i] = r;
  
        else
            a[i] = 9 - r;
  
        i++;
  
        // Reduce the number each time
        num = num / 10;
    }
  
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0)
    {
        System.out.print("9");
        i--;
    }
  
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        System.out.print(a[j]);
}
  
// Driver Code
public static void main(String []args)
{
    // Given Number
     int num = 4545;
  
    // Function Call
    number(num);
}
}
 
// This code is contributed by rock_cool

Python3

# Python3 program for the above approach
 
# Function to invert the digits of
# integer N to form minimum
# possible number
def number(num):
   
    # Initialize the array
    a = [0] * 20
    r, i, j = 0, 0, 0
 
    # Iterate till the number N exists
    while (num > 0):
 
        # Last digit of the number N
        r = num % 10
 
        # Checking if the digit is
        # smaller than 9-digit
        if (9 - r > r):
 
            # Store the smaller
            # digit in the array
            a[i] = r
 
        else:
            a[i] = 9 - r
 
        i += 1
 
        # Reduce the number each time
        num = num // 10
 
    # Check if the digit starts
    # with 0 or not
    if (a[i - 1] == 0):
        print(9, end = "")
        i -= 1
 
    # Print the answer
    for j in range(i - 1, -1, -1):
        print(a[j], end = "")
 
# Driver Code
if __name__ == '__main__':
   
    # Given Number
    num = 4545
 
    # Function Call
    number(num)
 
# This code is contributed by Mohit Kumar

C#

// C# program for the above approach
using System;
class GFG{
   
// Function to invert the digits of
// integer N to form minimum
// possible number
static void number(int num)
{
    // Initialize the array
    int[] a = new int[20];
    int r, i = 0, j;
   
    // Iterate till the number N exists
    while (num > 0)
    {
   
        // Last digit of the number N
        r = num % 10;
   
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
   
            // Store the smaller
            // digit in the array
            a[i] = r;
   
        else
            a[i] = 9 - r;
   
        i++;
   
        // Reduce the number each time
        num = num / 10;
    }
   
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0)
    {
        Console.Write("9");
        i--;
    }
   
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        Console.Write(a[j]);
}
   
// Driver Code
public static void Main(string []args)
{
    // Given Number
     int num = 4545;
   
    // Function Call
    number(num);
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to invert the digits of
// integer N to form minimum
// possible number
function number(num)
{
     
    // Initialize the array
    let a = new Array(20);
    let r, j;
    let i = 0;
 
    // Iterate till the number N exists
    while (num > 0)
    {
         
        // Last digit of the number N
        r = num % 10;
 
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
 
            // Store the smaller
            // digit in the array
            a[i] = r;
 
        else
            a[i] = 9 - r;
 
        i++;
 
        // Reduce the number each time
        num = parseInt(num / 10, 10);
    }
 
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0)
    {
        document.write(9);
        i--;
    }
 
    // Print the answer
    for(j = i - 1; j >= 0; j--)
        document.write(a[j]);
}
 
// Driver code
 
// Given Number
let num = 4545;
 
// Function Call
number(num);
 
// This code is contributed by divyesh072019
 
</script>
Producción

4444

Complejidad de tiempo: O(log 10 N)
Espacio auxiliar: O(log 10 N)

Enfoque alternativo: para obtener el número mínimo, necesitamos convertir todos los dígitos a su mínimo, para que podamos obtener el número mínimo después de restar 4,3,2,1. 

Reason-: We can only get 4 or 3 or 2 or 1 or 0 minimals after subtracting any digit from 9 so If we have 5 or 6 
or 7 or 8 at the first digit then after subtracting from 9 we can get 4 or 3 or 2 or 1, and if these are not
present then that means that we already have minimum 4 or 3 or 2 or 1 at the first digit.

Por lo tanto, verificaremos cada s[i] si 4<s[i]<9, luego restaremos s[i] de 9 y, por lo tanto, obtendremos el resultado deseado.

C++

#include <bits/stdc++.h>
using namespace std;
 
string solve(string s)
{
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if (s[0] != '9' && s[0] > '4') {
        s[0] = '0' + ('9' - s[0]);
    }
 
    // Check for every s[i] from
    // 1 to s.length that 4 < s[i]
    // < 9
    for (int i = 1; i < s.size(); i++) {
        if (s[i] > '4')
            s[i] = '0' + ('9' - s[i]);
    }
    return s;
}
int main()
{
    string s = "27";
    cout << solve(s);
    return 0;
};

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  static String solve(String s)
  {
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if (s.charAt(0) != '9' && (int)s.charAt(0) > (int)'4') {
      s = (char)((int)'0' + ((int)'9' - (int)s.charAt(0))) +
        s.substring(1, s.length());
    }
 
    // // Check for every s[i] from
    // // 1 to s.length that 4 < s[i]
    // // < 9
    for (int i = 1; i < s.length(); i++) {
      if ((int)s.charAt(i) > (int)'4')
        s = s.substring(0, i) + (char)((int)'0' + ((int)'9' - (int)s.charAt(i))) + s.substring(i+1,s.length());
    }
    return s;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    String s = "27";
    System.out.println(solve(s));
  }
}
 
// This code is contributed by shinjanpatra.

Python3

# Python code for the approach
def solve(s):
 
    # If 4 < s[0] < 9 then subtract to
    # Get the minimum number
    if ord(s[0]) != ord('9') and ord(s[0]) > ord('4'):
        s = s.replace(s[0] , chr(ord('0') + ord('9') - ord(s[0])))
 
    # Check for every s[i] from
    # 1 to s.length that 4 < s[i]
    # < 9
    for i in range(1,len(s)):
        if (s[i] > '4'):
            s = s.replace(s[i] , chr(ord('0') + (ord('9') - ord(s[i]))))
 
    return s
 
# driver code
s = "27"
print(solve(s))
 
# This code is contributed by shinjanpatra

Javascript

<script>
 
// JavaScript code for the approach
function solve(s)
{
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if(s.charCodeAt(0) != '9'.charCodeAt(0) && s.charCodeAt(0) > '4'.charCodeAt(0))
        s = s.replace(s[0] , String.fromCharCode('0'.charCodeAt(0) + '9'.charCodeAt(0) - s.charCodeAt(0)))
 
    // Check for every s[i] from
    // 1 to s.length that 4 < s[i]
    // < 9
    for(let i = 1; i < s.length; i++)
    {
        if (s[i] > '4')
        s = s.replace(s[i] , String.fromCharCode('0'.charCodeAt(0) + '9'.charCodeAt(0) - s.charCodeAt(i)))
    }
 
    return s
}
 
// driver code
let s = "27"
document.write(solve(s))
 
// This code is contributed by shinjanpatra
 
</script>
Producción

22

COMPLEJIDAD DE TIEMPO – O(N)

COMPLEJIDAD ESPACIAL – O(1)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *