Entero mínimo que se puede obtener intercambiando dígitos adyacentes de diferente paridad

Dado un número entero N , la tarea es encontrar el número entero mínimo que se puede obtener a partir del número entero dado, de modo que los dígitos adyacentes de diferente paridad se puedan intercambiar cualquier número de veces. 
Dos dígitos de paridad diferente significa que tendrán residuos diferentes cuando se dividen por dos.
Ejemplos: 
 

Entrada: N = 64432 
Salida: 36442 
Explicación: 
Intercambiar el cuarto y el tercer dígito; N = 64342 
Intercambiar el 3er y 2do dígito; N = 63442 
Intercambiar el segundo y el primer dígito; N = 36442
Entrada: 
3137 
Salida: 
3137 
 

Enfoque: La idea del enfoque es usar dos pilas para mantener los dígitos del número. 
 

• En una pila, se pueden almacenar números que son divisibles por dos.
• En otra pila, se pueden almacenar números que no son divisibles por dos.
• Luego, los elementos se empujan en ambas pilas en orden inverso al número.
• Ahora, el elemento de la pila cuya parte superior contiene el elemento más pequeño se extrae y se concatena con la respuesta hasta que una de las pilas está vacía.
• Luego, los elementos restantes de la pila se concatenan, que no está vacío con la respuesta, y finalmente se devuelve la salida.

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

// C++ implementation of the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum number
int minimumNo(int n)
{
    int ans = 0;
    stack<int> stack1;
    stack<int> stack2;
    while (n != 0) {
        int r = n % 10;
 
        // Store the elements which are
        // divisible by two in stack1
        if (r % 2 == 0) {
            stack1.push(r);
        }
 
        // Store the elements which are
        // not divisible by two in stack2.
        else {
            stack2.push(r);
        }
        n = n / 10;
    }
 
    while (!stack1.empty() && !stack2.empty()) {
 
        // Concatenate the answer with smaller value
        // of the topmost elements of both the
        // stacks and then pop that element
        if (stack1.top() < stack2.top()) {
            ans = ans * 10 + stack1.top();
            stack1.pop();
        }
        else {
            ans = ans * 10 + stack2.top();
            stack2.pop();
        }
    }
 
    // Concatenate the answer with remaining
    // values of stack1.
    while (!stack1.empty()) {
        ans = ans * 10 + stack1.top();
        stack1.pop();
    }
 
    // Concatenate the answer with remaining
    // values of stack2.
    while (!stack2.empty()) {
        ans = ans * 10 + stack2.top();
        stack2.pop();
    }
    return ans;
}
 
// Driver code
int main()
{
    int n1 = 64432;
 
    // Function calling
    cout << minimumNo(n1) << endl;
 
    int n2 = 3137;
    cout << minimumNo(n2) << endl;
 
    return 0;
}

// Java implementation of the above approach.
import java.util.*;
 
class GFG
{
     
// Function to return the minimum number
static int minimumNo(int n)
{
    int ans = 0;
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    while (n != 0)
    {
        int r = n % 10;
 
        // Store the elements which are
        // divisible by two in stack1
        if (r % 2 == 0)
        {
            stack1.add(r);
        }
 
        // Store the elements which are
        // not divisible by two in stack2.
        else
        {
            stack2.add(r);
        }
        n = n / 10;
    }
 
    while (!stack1.isEmpty() && !stack2.isEmpty())
    {
 
        // Concatenate the answer with smaller value
        // of the topmost elements of both the
        // stacks and then pop that element
        if (stack1.peek() < stack2.peek())
        {
            ans = ans * 10 + stack1.peek();
            stack1.pop();
        }
        else
        {
            ans = ans * 10 + stack2.peek();
            stack2.pop();
        }
    }
 
    // Concatenate the answer with remaining
    // values of stack1.
    while (!stack1.isEmpty())
    {
        ans = ans * 10 + stack1.peek();
        stack1.pop();
    }
 
    // Concatenate the answer with remaining
    // values of stack2.
    while (!stack2.isEmpty())
    {
        ans = ans * 10 + stack2.peek();
        stack2.pop();
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int n1 = 64432;
 
    // Function calling
    System.out.print(minimumNo(n1) + "\n");
 
    int n2 = 3137;
    System.out.print(minimumNo(n2) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the above approach.
 
# Function to return the minimum number
def minimumNo(n):
    ans = 0
    stack1 = []
    stack2 = []
    while (n != 0):
        r = n % 10
 
        # Store the elements which are
        # divisible by two in stack1
        if (r % 2 == 0):
            stack1.append(r)
 
        # Store the elements which are
        # not divisible by two in stack2.
        else :
            stack2.append(r)
 
        n = n // 10
    while (len(stack1) > 0 and len(stack2) > 0):
 
        # Concatenate the answer with smaller value
        # of the topmost elements of both the
        # stacks and then pop that element
        if (stack1[-1] < stack2[-1]):
            ans = ans * 10 + stack1[-1]
            del stack1[-1]
 
        else:
            ans = ans * 10 + stack2[-1]
            del stack2[-1]
 
    # Concatenate the answer with remaining
    # values of stack1.
    while (len(stack1) > 0):
        ans = ans * 10 + stack1[-1]
        del stack1[-1]
 
    # Concatenate the answer with remaining
    # values of stack2.
    while (len(stack2) > 0):
        ans = ans * 10 + stack2[-1]
        del stack2[-1]
 
    return ans
 
# Driver code
n1 = 64432
 
# Function calling
print(minimumNo(n1))
 
n2 = 3137
print(minimumNo(n2))
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach.
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to return the minimum number
static int minimumNo(int n)
{
    int ans = 0;
    Stack<int> stack1 = new Stack<int>();
    Stack<int> stack2 = new Stack<int>();
    while (n != 0)
    {
        int r = n % 10;
 
        // Store the elements which are
        // divisible by two in stack1
        if (r % 2 == 0)
        {
            stack1.Push(r);
        }
 
        // Store the elements which are
        // not divisible by two in stack2.
        else
        {
            stack2.Push(r);
        }
        n = n / 10;
    }
 
    while (stack1.Count != 0 && stack2.Count != 0)
    {
 
        // Concatenate the answer with smaller value
        // of the topmost elements of both the
        // stacks and then pop that element
        if (stack1.Peek() < stack2.Peek())
        {
            ans = ans * 10 + stack1.Peek();
            stack1.Pop();
        }
        else
        {
            ans = ans * 10 + stack2.Peek();
            stack2.Pop();
        }
    }
 
    // Concatenate the answer with remaining
    // values of stack1.
    while (stack1.Count != 0)
    {
        ans = ans * 10 + stack1.Peek();
        stack1.Pop();
    }
 
    // Concatenate the answer with remaining
    // values of stack2.
    while (stack2.Count != 0)
    {
        ans = ans * 10 + stack2.Peek();
        stack2.Pop();
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int n1 = 64432;
 
    // Function calling
    Console.Write(minimumNo(n1) + "\n");
 
    int n2 = 3137;
    Console.Write(minimumNo(n2) + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
      // JavaScript implementation
      // of the above approach.
       
      // Function to return the minimum number
      function minimumNo(n) {
        var ans = 0;
        var stack1 = [];
        var stack2 = [];
        while (n !== 0) {
          var r = n % 10;
 
          // Store the elements which are
          // divisible by two in stack1
          if (r % 2 === 0) {
            stack1.push(r);
          }
 
          // Store the elements which are
          // not divisible by two in stack2.
          else {
            stack2.push(r);
          }
          n = parseInt(n / 10);
        }
 
        while (stack1.length !== 0 && stack2.length !== 0)
        {
          // Concatenate the answer with smaller value
          // of the topmost elements of both the
          // stacks and then pop that element
          if (stack1[stack1.length - 1] <
          stack2[stack2.length - 1]) {
            ans = ans * 10 + stack1[stack1.length - 1];
            stack1.pop();
          } else {
            ans = ans * 10 + stack2[stack2.length - 1];
            stack2.pop();
          }
        }
 
        // Concatenate the answer with remaining
        // values of stack1.
        while (stack1.length !== 0) {
          ans = ans * 10 + stack1[stack1.length - 1];
          stack1.pop();
        }
 
        // Concatenate the answer with remaining
        // values of stack2.
        while (stack2.length !== 0) {
          ans = ans * 10 + stack2[stack2.length - 1];
          stack2.pop();
        }
        return ans;
      }
 
      // Driver code
      var n1 = 64432;
 
      // Function calling
      document.write(minimumNo(n1) + "<br>");
 
      var n2 = 3137;
      document.write(minimumNo(n2) + "<br>");
       
</script>

36442
3137

Complejidad de Tiempo: O(logN)
Espacio Auxiliar : O(logN).