Minimiza el número formado reemplazando un par de dígitos adyacentes con su suma

Posted on by Rudeus Greyrat

Dada la string s que denota un número. La tarea es encontrar el número mínimo que se puede formar después de reemplazar dos dígitos consecutivos de s por su suma.

Ejemplos:

Entrada: s = “1005”
Salida: 105
Explicación: Seleccione y reemplace dos dígitos consecutivos con su suma 

Entrada: s = “ 56773″
Salida: 11773
Explicación: Seleccione y reemplace los primeros dos dígitos consecutivos (5 y 6) con su suma (11) 

 

Enfoque:  este problema se puede resolver utilizando el enfoque codicioso . Utilice la siguiente observación:

Si existe al menos un par que tenga una suma menor que 10 :

  • La suma siempre será mayor o igual a los elementos del par adyacente.
  • Entonces, reemplazar la última llegada de dicho par dará el número mínimo posible. De lo contrario, el número aumentará.
  • Por ejemplo, 2381 se puede hacer 581 o 239 y 239 es el mínimo entre estos dos.
  • Esta condición tiene prioridad porque disminuye el número de dígitos del número y hace que el valor sea menor que cualquier número que tenga el mismo número de dígitos que el número real.

Si no hay tal par que tenga una suma menor que 10 :

  • La suma siempre será menor que el número formado por los dígitos adyacentes.
  • Entonces, reemplazar la primera aparición de tal par dará el número mínimo, ya que hace que la parte más significativa sea mínima.
  • Por ejemplo, 386 puede convertirse en 116 o 314. 116 es el menor.

Siga los pasos a continuación para resolver el problema dado usando la observación anterior.

  • En primer lugar suponga que existe al menos un par de elementos consecutivos cuya suma es menor que 10 .
    • Iterar la string numérica desde atrás .
    • Encuentra el primer par de dígitos consecutivos cuya suma sea menor que 10 .
    • Reemplácelos con su suma y devuelva la string .
  • Ahora, maneje los casos en los que no haya un solo par de elementos consecutivos cuya suma sea menor que 10 .
    • Iterar la string numérica desde el principio .
    • El primer par de dígitos consecutivos cuya suma sea igual o mayor que 10 es la respuesta óptima.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number after
// doing given operation
void findSmallestNumber(string str, int N)
{
    string ans = "";
    bool found = false;
 
    // Iterate through the string in
    // reverse order
    for (int i = N - 1; i >= 1; i--) {
        int a = (str[i] - '0');
        int b = (str[i - 1] - '0');
        if (a + b < 10) {
            found = true;
            ans = str.substr(0, i - 1);
            int sum = a + b;
            int last = sum % 10;
            char l = last + '0';
            sum /= 10;
 
            if (sum != 0) {
                char p = sum + '0';
                ans.push_back(p);
            }
            ans.push_back(l);
            ans += str.substr(i + 1,
                              N - i - 1);
            cout << ans;
            break;
        }
    }
 
    if (!found) {
        int sum = (str[0] - '0')
                  + (str[1] - '0');
        ans = (char)(sum / 10 + '0');
        sum %= 10;
        ans += (sum + '0');
        ans += str.substr(2, N - 2);
        cout << ans;
    }
}
 
// Driver code
int main()
{
    string s = "56773";
    int N = s.length();
 
    // Function Call
    findSmallestNumber(s, N);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG
{
 
  // Function to find minimum number after
  // doing given operation
  static void findSmallestNumber(String str, int N)
  {
    String ans = "";
    boolean found = false;
 
    // Iterate through the string in
    // reverse order
    for (int i = N - 1; i >= 1; i--) {
      int a = (str.charAt(i) - '0');
      int b = (str.charAt(i-1)- '0');
      if (a + b < 10) {
        found = true;
        ans = str.substring(0, i - 1);
        int sum = a + b;
        int last = sum % 10;
        char l = (char)(last + '0');
        sum /= 10;
 
        if (sum != 0) {
          char p = (char)(sum + '0');
          ans += p;
        }
        ans += l;
        ans += str.substring(i + 1,
                             N - i - 1);
        System.out.println(ans);
        break;
      }
    }
 
    if (!found) {
      int sum = (str.charAt(0) - '0')
        + (str.charAt(1) - '0');
      Integer num = sum / 10;
      ans = num.toString();
      Integer summ = sum % 10;
      ans += summ.toString();
      ans += str.substring(2, N );
      System.out.println(ans);
    }
  }
 
// Driver Code
public static void main(String args[])
{
    String s = "56773";
    int N = s.length();
 
    // Function Call
    findSmallestNumber(s, N);
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program for the above approach
 
# Function to find minimum number after
# doing given operation
def findSmallestNumber(str, N):
    ans = ""
    found = False
 
    # Iterate through the string in
    # reverse order
    for i in range(N - 1, 1, -1):
        a = (ord(str[i]) - ord('0'))
        b = (ord(str[i - 1]) - ord('0'))
        if (a + b < 10):
            found = True
            ans = str[0: i - 1]
            sum = a + b
            last = sum % 10
            l = (str)(last)
            sum = sum // 10
 
            if (sum != 0):
                p = (str)(sum)
                ans += p
 
            ans += (l)
            ans += str[i + 1: i + 1 + N - i - 1]
            print(ans)
            break
 
    if (not found):
        sum = (ord(str[0]) - ord('0')) + (ord(str[1]) - ord('0'))
        ans = f'{sum // 10}'
 
        sum %= 10
        ans += f'{sum}'
        ans += str[2: 2 + N - 2]
        print(ans)
 
# Driver code
s = "56773"
N = len(s)
 
# Function Call
findSmallestNumber(s, N)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG
{
  // Function to find minimum number after
  // doing given operation
  static void findSmallestNumber(string str, int N)
  {
    string ans = "";
    bool found = false;
 
    // Iterate through the string in
    // reverse order
    for (int i = N - 1; i >= 1; i--) {
      int a = (str[i] - '0');
      int b = (str[i - 1] - '0');
      if (a + b < 10) {
        found = true;
        ans = str.Substring(0, i - 1);
        int sum = a + b;
        int last = sum % 10;
        char l = (char)(last + '0');
        sum /= 10;
 
        if (sum != 0) {
          char p = (char)(sum + '0');
          ans += p;
        }
        ans += l;
        ans += str.Substring(i + 1,
                             N - i - 1);
        Console.Write(ans);
        break;
      }
    }
 
    if (!found) {
      int sum = (str[0] - '0')
        + (str[1] - '0');
      int num = sum / 10;
      ans = num.ToString();
      sum %= 10;
      ans += sum.ToString();
      ans += str.Substring(2, N - 2);
      Console.Write(ans);
    }
  }
 
  // Driver code
  public static void Main()
  {
    string s = "56773";
    int N = s.Length;
 
    // Function Call
    findSmallestNumber(s, N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find minimum number after
    // doing given operation
    const findSmallestNumber = (str, N) => {
        let ans = "";
        let found = false;
 
        // Iterate through the string in
        // reverse order
        for (let i = N - 1; i >= 1; i--) {
            let a = (str.charCodeAt(i) - '0'.charCodeAt(0));
            let b = (str.charCodeAt(i - 1) - '0'.charCodeAt(0));
            if (a + b < 10) {
                found = true;
                ans = str.substring(0, i - 1);
                let sum = a + b;
                let last = sum % 10;
                let l = last.toString();
                sum = parseInt(sum / 10);
 
                if (sum != 0) {
                    let p = sum.toString();
                    ans += p;
                }
                ans += (l);
                ans += str.substring(i + 1, i + 1 + N - i - 1);
                document.write(ans);
                break;
            }
        }
 
        if (!found) {
            let sum = (str.charCodeAt(0) - '0'.charCodeAt(0))
                + (str.charCodeAt(1) - '0'.charCodeAt(0));
            ans = (parseInt(sum / 10)).toString();
 
            sum %= 10;
            ans += sum.toString();
            ans += str.substring(2, 2 + N - 2);
            document.write(ans);
        }
    }
 
    // Driver code
    let s = "56773";
    let N = s.length;
 
    // Function Call
    findSmallestNumber(s, N);
 
 // This code is contributed by rakeshsahni
 
</script>
Producción

11773

Complejidad de tiempo: O(N) donde N es el tamaño de la string
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por bhuwanesh 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 *