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