El número más pequeño posible intercambiando pares impares adyacentes

Posted on by Rudeus Greyrat

Dada una string numérica str , la tarea es encontrar el entero más pequeño que se puede formar intercambiando dígitos adyacentes de paridad distinta. Ejemplos:

Entrada: 836360 Salida: 338660 Explicación: 1.er intercambio: 83 6360 -> 386360 2.º intercambio: 38 63 60 -> 383660 3.er intercambio: 3 83 660 -> 338660 Entrada: 1003 Salida: 13

Enfoque: podemos observar que en intercambios repetidos, podemos dividir los dígitos pares e impares de str en dos bloques separados. El orden de los dígitos en sus respectivos bloques será el mismo que su orden de aparición en la string, ya que no se permite el intercambio dentro de un bloque ( misma paridad ). Por lo tanto, después de separar str en dos bloques separados, necesitamos atravesar estos dos bloques y agregar el mínimo de los dos valores señalados actualmente a la respuesta. La string final generada después de esta operación, seguida de la eliminación de los 0 iniciales, si los hay, es la respuesta requerida. Ejemplo:Los bloques pares e impares en el orden de aparición en 836360 son {8, 6, 6, 0} y {3, 3} respectivamente. Por lo tanto, el número más pequeño y formado es el siguiente:

  1. respuesta = respuesta + min(8, 3) => respuesta = 3
  2. respuesta = respuesta + min(8, 3) => respuesta = 33
  3. Dado que todos los dígitos impares están agotados, los dígitos pares restantes deben agregarse uno por uno.
  4. Por lo tanto, la respuesta requerida es 338660

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

C++

// C++ Program to find the
// smallest number possible
// by swapping adjacent digits
// of different parity
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// smallest number possible
string findAns(string s)
{
    int digit;
 
    // Arrays to store odd and
    // even digits in the order
    // of their appearance in
    // the given string
    vector<int> odd;
    vector<int> even;
 
    // Insert the odd and
    // even digits
    for (auto c : s) {
        digit = c - '0';
        if (digit & 1)
            odd.push_back(digit);
        else
            even.push_back(digit);
    }
 
    // pointer to odd digit
    int i = 0;
    // pointer to even digit
    int j = 0;
 
    string ans = "";
 
    while (i < odd.size()
           and j < even.size()) {
 
        if (odd[i] < even[j])
            ans += (char)(odd[i++] + '0');
        else
            ans += (char)(even[j++] + '0');
    }
 
    // In case number of even and
    // odd digits are not equal
 
    // If odd digits are remaining
    while (i < odd.size())
        ans += (char)(odd[i++] + '0');
 
    // If even digits are remaining
    while (j < even.size())
        ans += (char)(even[j++] + '0');
 
    // Removal of leading 0's
    while (ans[0] == '0') {
        ans.erase(ans.begin());
    }
 
    return ans;
}
int main()
{
 
    string s = "894687536";
    cout << findAns(s);
    return 0;
}

Java

// Java program to find the smallest
// number possible by swapping adjacent
// digits of different parity
import java.util.*;
 
class GFG{
 
// Function to return the
// smallest number possible
static String findAns(String s)
{
    int digit;
 
    // Arrays to store odd and even
    // digits in the order their
    // appearance in the given String
    Vector<Integer> odd =new Vector<Integer>();
    Vector<Integer> even = new Vector<Integer>();
 
    // Insert the odd and
    // even digits
    for(char c : s.toCharArray())
    {
       digit = c - '0';
       if (digit % 2 == 1)
           odd.add(digit);
       else
           even.add(digit);
    }
 
    // Pointer to odd digit
    int i = 0;
     
    // Pointer to even digit
    int j = 0;
 
    String ans = "";
 
    while (i < odd.size() && j < even.size())
    {
        if (odd.get(i) < even.get(j))
            ans += (char)(odd.get(i++) + '0');
        else
            ans += (char)(even.get(j++) + '0');
    }
 
    // In case number of even and
    // odd digits are not equal
    // If odd digits are remaining
    while (i < odd.size())
        ans += (char)(odd.get(i++) + '0');
 
    // If even digits are remaining
    while (j < even.size())
        ans += (char)(even.get(j++) + '0');
 
    // Removal of leading 0's
    while (ans.charAt(0) == '0')
    {
        ans = ans.substring(1);
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "894687536";
     
    System.out.print(findAns(s));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 Program to find the
# smallest number possible
# by swapping adjacent digits
# of different parity
 
# Function to return the
# smallest number possible
def findAns(s):
 
    # Arrays to store odd and
    # even digits in the order
    # of their appearance in
    # the given string
    odd = []
    even = []
 
    # Insert the odd and
    # even digits
         
    for c in s:
        digit = int(c)
        if (digit & 1):
            odd.append(digit)
        else:
            even.append(digit)
 
    # pointer to odd digit
    i = 0
     
    # pointer to even digit
    j = 0
 
    ans = ""
 
    while (i < len(odd) and j < len(even)):
         
        if (odd[i] < even[j]):
            ans += str(odd[i])
            i = i + 1
        else:
            ans += str(even[j])
            j = j + 1
 
    # In case number of even and
    # odd digits are not equal
 
    # If odd digits are remaining
    while (i < len(odd)):
        ans += str(odd[i])
        i = i + 1
 
    # If even digits are remaining
    while (j < len(even)):
        ans += str(even[j])
        j = j + 1
 
    # Removal of leading 0's
    while (ans[0] == '0'):
        ans = ans[1:]
 
    return ans
 
# Driver Code
s = "894687536"
print(findAns(s))
 
# This code is contributed by yatin

C#

// C# program to find the smallest
// number possible by swapping adjacent
// digits of different parity
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the
// smallest number possible
static String findAns(String s)
{
    int digit;
 
    // Arrays to store odd and even
    // digits in the order their
    // appearance in the given String
    List<int> odd = new List<int>();
    List<int> even = new List<int>();
 
    // Insert the odd and
    // even digits
    foreach(char c in s.ToCharArray())
    {
        digit = c - '0';
        if (digit % 2 == 1)
            odd.Add(digit);
        else
            even.Add(digit);
    }
 
    // Pointer to odd digit
    int i = 0;
     
    // Pointer to even digit
    int j = 0;
 
    String ans = "";
 
    while (i < odd.Count && j < even.Count)
    {
        if (odd[i] < even[j])
            ans += (char)(odd[i++] + '0');
        else
            ans += (char)(even[j++] + '0');
    }
 
    // In case number of even and
    // odd digits are not equal
    // If odd digits are remaining
    while (i < odd.Count)
        ans += (char)(odd[i++] + '0');
 
    // If even digits are remaining
    while (j < even.Count)
        ans += (char)(even[j++] + '0');
 
    // Removal of leading 0's
    while (ans[0] == '0')
    {
        ans = ans.Substring(1);
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "894687536";
     
    Console.Write(findAns(s));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program to find the smallest
// number possible by swapping adjacent
// digits of different parity
 
    // Function to return the
    // smallest number possible
     function findAns( s) {
        var digit;
 
        // Arrays to store odd and even
        // digits in the order their
        // appearance in the given String
        var odd = [];
        var even = [];
 
        // Insert the odd and
        // even digits
        for (var i =0;i<s.length;i++) {
            digit = s[i].charCodeAt(0) -'0'.charCodeAt(0);
            if (digit % 2 == 1)
                odd.push(digit);
            else
                even.push(digit);
        }
 
        // Pointer to odd digit
        var i = 0;
 
        // Pointer to even digit
        var j = 0;
 
        var ans = "";
 
        while (i < odd.length && j < even.length) {
            if (odd[i] < even[j])
                ans +=  String.fromCharCode(odd[i++] + '0'.charCodeAt(0));
            else
                ans += String.fromCharCode(even[j++] + '0'.charCodeAt(0));
        }
 
        // In case number of even and
        // odd digits are not equal
        // If odd digits are remaining
        while (i < odd.length)
            ans +=  String.fromCharCode(odd[i++] + '0'.charCodeAt(0));
 
        // If even digits are remaining
        while (j < even.length)
            ans +=  String.fromCharCode(even[j++] + '0'.charCodeAt(0));
 
        // Removal of leading 0's
        while (ans.charAt(0) == '0') {
            ans = ans.substring(1);
        }
        return ans;
    }
 
    // Driver code
        var s = "894687536";
        document.write(findAns(s));
 
// This code is contributed by gauravrajput1
</script>
Producción:

846869753

Complejidad de tiempo: O(N) , donde N es el tamaño de la string dada.

Publicación traducida automáticamente

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