Dada una string N y un dígito X ([1, 9]) , la tarea es encontrar el número entero mínimo formado al insertar el dígito X en cualquier parte de N.
Ejemplos:
Entrada: N = “89”, X = 1
Salida: “ 189″
Explicación: X se puede insertar en 3 posiciones {189, 891, 819} y 189 es el mínimo.Entrada: N = “-12”, X = 3
Salida: “- 312″
Enfoque ingenuo: un enfoque simple para este problema es insertar X en todas las posiciones (excepto a la izquierda del signo negativo, si está presente) y encontrar el mínimo entre todos los números formados. El enfoque es ineficiente en el caso de strings más grandes.
Enfoque eficiente: la idea principal es que si N es un número positivo, inserte de tal manera que el número formado sea mínimo , mientras que si N es negativo, entonces inserte en X de tal manera que el número formado sea máximo , ignorando el signo negativo. Siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice dos variables, digamos len = longitud de la string N y position = n + 1 .
- Si N es negativo ( N[0] = ‘-‘), recorra la string desde (n-1) th index hasta 1th index y verifique si N[i] – ‘0’ < X, si es verdadero, entonces actualice la posición = yo _
- Si N es positivo , recorra la string desde (n-1) el índice th hasta el índice 0th y verifique si N[i] – ‘0’ > X, si es verdadero, entonces actualice la posición = i .
- Inserte X en la posición de índice en N .
- Finalmente, devuelve la string N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to insert X in N and
// return the minimum value string
string MinValue(string N, int X)
{
// Variable to store length
// of string N
int len = N.size();
// Variable to denote the position
// where X must be added
int position = len + 1;
// If the given string N represent
// a negative value
if (N[0] == '-') {
// X must be place at the last
// index where is greater than N[i]
for (int i = len - 1; i >= 1; i--) {
if ((N[i] - '0') < X) {
position = i;
}
}
}
else {
// For positive numbers, X must be
// placed at the last index where
// it is smaller than N[i]
for (int i = len - 1; i >= 0; i--) {
if ((N[i] - '0') > X) {
position = i;
}
}
}
// Insert X at that position
N.insert(N.begin() + position, X + '0');
// Return the string
return N;
}
// Driver Code
int main()
{
// Given Input
string N = "89";
int X = 1;
// Function Call
cout << MinValue(N, X) << "\n";
}
Java
// Java implementation of above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to insert X in N and
// return the minimum value string
static String MinValue(String number, int x)
{
// Variable to store length
// of string N
int length = number.length();
// Variable to denote the position
// where X must be added
int position = length + 1;
// If the given string N represent
// a negative value
if (number.charAt(0) == '-') {
// X must be place at the last
// index where is greater than N[i]
for (int i = number.length() - 1; i >= 1; --i) {
if ((number.charAt(i) - 48) < x) {
position = i;
}
}
}
else {
// For positive numbers, X must be
// placed at the last index where
// it is smaller than N[i]
for (int i = number.length() - 1; i >= 0; --i) {
if ((number.charAt(i) - 48) > x) {
position = i;
}
}
}
// Insert X at that position
number
= number.substring(0, position) + x
+ number.substring(position, number.length());
// return string
return number.toString();
}
// Driver call
public static void main(String[] args)
{
// given input
String number = "89";
int x = 1;
// function call
System.out.print(MinValue(number, x));
}
}
// This code is contributed by zack_aayush.
Python3
# Python Program for the above approach
# Function to insert X in N and
# return the minimum value string
def MinValue(N, X):
# Variable to store length
# of string N
N = list(N);
ln = len(N)
# Variable to denote the position
# where X must be added
position = ln + 1
# If the given string N represent
# a negative value
if (N[0] == '-'):
# X must be place at the last
# index where is greater than N[i]
for i in range(ln - 1, 0, -1):
if ((ord(N[i]) - ord('0')) < X):
position = i
else:
# For positive numbers, X must be
# placed at the last index where
# it is smaller than N[i]
for i in range(ln - 1, -1, -1):
if ((ord(N[i]) - ord('0')) > X):
position = i
# Insert X at that position
c = chr(X + ord('0'))
str = N.insert(position, c);
# Return the string
return ''.join(N)
# Driver Code
# Given Input
N = "89"
X = 1
# Function Call
print(MinValue(N, X))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG {
// Function to insert X in N and
// return the minimum value string
static String MinValue(string number, int x)
{
// Variable to store length
// of string N
int length = number.Length;
// Variable to denote the position
// where X must be added
int position = length + 1;
// If the given string N represent
// a negative value
if (number[0] == '-') {
// X must be place at the last
// index where is greater than N[i]
for (int i = number.Length - 1; i >= 1; --i) {
if ((number[i] - 48) < x) {
position = i;
}
}
}
else {
// For positive numbers, X must be
// placed at the last index where
// it is smaller than N[i]
for (int i = number.Length - 1; i >= 0; --i) {
if ((number[i] - 48) > x) {
position = i;
}
}
}
// Insert X at that position
number
= number.Substring(0, position) + x
+ number.Substring(position, number.Length);
// return string
return number.ToString();
}
// Driver code
public static void Main()
{
// given input
string number = "89";
int x = 1;
// function call
Console.WriteLine(MinValue(number, x));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript Program for the above approach
// Function to insert X in N and
// return the minimum value string
function MinValue(N, X) {
// Variable to store length
// of string N
let len = N.length;
// Variable to denote the position
// where X must be added
let position = len + 1;
// If the given string N represent
// a negative value
if (N[0] == '-') {
// X must be place at the last
// index where is greater than N[i]
for (let i = len - 1; i >= 1; i--) {
if ((N[i].charCodeAt(0) - '0'.charCodeAt(0)) < X) {
position = i;
}
}
}
else {
// For positive numbers, X must be
// placed at the last index where
// it is smaller than N[i]
for (let i = len - 1; i >= 0; i--) {
if ((N[i].charCodeAt(0) - '0'.charCodeAt(0)) > X) {
position = i;
}
}
}
// Insert X at that position
const c = String.fromCharCode(X + '0'.charCodeAt(0));
let str = N.slice(0, position) + c + N.slice(position);
// Return the string
return str;
}
// Driver Code
// Given Input
let N = "89";
let X = 1;
// Function Call
document.write(MinValue(N, X));
// This code is contributed by Potta Lokesh
</script>
Producción
189
Complejidad temporal: O(N)
Espacio auxiliar: O(1)