Siguiente número más alto utilizando al menos una operación de intercambio

Dado un número no negativo num . El problema es encontrar el número más pequeño mayor que num realizando como máximo una operación de intercambio entre dos dígitos en num . Si no se puede formar un número mayor, escriba «No es posible».
El número podría ser muy grande y es posible que ni siquiera encaje en long long int.

Ejemplos: 

Input : num = "218765"
Output : 258761
We swap 5 and 1 to get the smallest
number greater than 'num'

Input : num = "541322"
Output : 542312

Enfoque: Primero encuentre el índice del dígito más a la derecha que tiene un dígito más grande que él y está del lado derecho. Sea su índice ind . Ahora, encuentra el índice del dígito más pequeño mayor que el dígito en el índice ind y es correcto. Sea su índice greatSmallDgt . Finalmente intercambie los dígitos en los índices ind y greatSmallDgt . Si los dígitos de num están en orden decreciente, imprima «No es posible».

Implementación:

// C++ implementation to find the next higher number
// using atmost one swap operation
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the next higher number
// using atmost one swap operation
string nxtHighUsingAtMostOneSwap(string num)
{
    int l = num.size();
 
    // to store the index of the largest digit
    // encountered so far from the right
    int posRMax = l - 1;
 
    // to store the index of rightmost digit
    // which has a digit greater to it on its
    // right side
    int index = -1;
 
    // finding the 'index' of rightmost digit
    // which has a digit greater to it on its
    // right side
    for (int i = l - 2; i >= 0; i--) {
        if (num[i] >= num[posRMax])
            posRMax = i;
 
        // required digit found, store its
        // 'index' and break
        else {
            index = i;
            break;
        }
    }
 
    // if no such digit is found which has a
    // larger digit on its right side
    if (index == -1)
        return "Not Possible";
 
    // to store the index of the smallest digit
    // greater than the digit at 'index' and right
    // to it
    int greatSmallDgt = -1;
 
    // finding the index of the smallest digit
    // greater than the digit at 'index'
    // and right to it
    for (int i = l - 1; i > index; i--) {
        if (num[i] > num[index]) {
            if (greatSmallDgt == -1)
                greatSmallDgt = i;
            else if (num[i] <= num[greatSmallDgt])
                greatSmallDgt = i;
        }
    }
 
    // swapping the digits
    char temp = num[index];
    num[index] = num[greatSmallDgt];
    num[greatSmallDgt] = temp;
 
    // required number
    return num;
}
 
// Driver program to test above
int main()
{
    string num = "218765";
    cout << "Original number: " << num << endl;
    cout << "Next higher number: "
         << nxtHighUsingAtMostOneSwap(num);
    return 0;
}

// JAVA implementation to find the next higher
// number using atmost one swap operation
class GFG{
     
    // function to find the next higher number
    // using atmost one swap operation
    static String nextHighUsingAtMostOneSwap(String st)
    {
        char num[] = st.toCharArray();
        int l = num.length;
          
        // to store the index of the largest digit
        // encountered so far from the right
        int posRMax = l - 1;
          
        // to store the index of rightmost digit
        // which has a digit greater to it on its
        // right side
        int index = -1;
          
        // finding the 'index' of rightmost digit
        // which has a digit greater to it on its
        // right side
        for (int i = l - 2; i >= 0; i--)
        {
            if (num[i] >= num[posRMax])
                posRMax = i;
              
            // required digit found, store its
            // 'index' and break   
            else
            {
                index = i;
                break;
            }   
        }
          
        // if no such digit is found which has a
        // larger digit on its right side
        if (index == -1)
            return "Not Possible";
          
        // to store the index of the smallest digit
        // greater than the digit at 'index' and
        // right to it   
        int greatSmallDgt = -1;
          
        // finding the index of the smallest
        // digit greater than the digit at
        // 'index' and right to it   
        for (int i = l - 1; i > index; i--)   
        {
            if (num[i] > num[index])
            {
                if (greatSmallDgt == -1)
                    greatSmallDgt = i;
                else if (num[i] <= num[greatSmallDgt])   
                    greatSmallDgt = i;
            }
        }
          
        // swapping the digits
        char temp = num[index];
         num[index] = num[greatSmallDgt];
        num[greatSmallDgt] = temp;
          
        // required number
        return (String.valueOf(num));
    }
      
    // Driver program to test above
    public static void main(String[] args)
    {
        String num = "218765";
        System.out.println("Original number: "
                           + num );
        System.out.println("Next higher number: "
              + nextHighUsingAtMostOneSwap(num));
    }
     
}
/*This code is contributed by Nikita Tiwari*/

# Python implementation to find the next higher
# number using atmost one swap operation
 
# function to find the next higher number
# using atmost one swap operation
def nextHighUsingAtMostOneSwap(st) :
    num = list (st)
    l = len(num)
     
    # to store the index of the largest digit
    # encountered so far from the right
    posRMax = l - 1
          
    # to store the index of rightmost digit
    # which has a digit greater to it on its
    # right side
    index = -1
          
    # finding the 'index' of rightmost digit
    # which has a digit greater to it on its
    # right side
    i = l - 2
    while i >= 0 :
        if (num[i] >= num[posRMax]) :
            posRMax = i
              
        # required digit found, store its
        # 'index' and break   
        else :
            index = i
            break
        i = i - 1
          
    # if no such digit is found which has
    # a larger digit on its right side
    if (index == -1) :
        return "Not Possible"
          
    # to store the index of the smallest digit
    # greater than the digit at 'index' and
    # right to it   
    greatSmallDgt = -1
          
    # finding the index of the smallest digit
    # greater than the digit at 'index'
    # and right to it   
    i = l - 1
    while i > index :
        if (num[i] > num[index]) :
            if (greatSmallDgt == -1) :
                greatSmallDgt = i
            else if (num[i] <= num[greatSmallDgt]) :
                greatSmallDgt = i
             
        i = i - 1
          
    # swapping the digits
    temp = num[index]
    num[index] = num[greatSmallDgt];
    num[greatSmallDgt] = temp;
          
    # required number
    return ''.join(num)
     
     
# Driver program to test above
num = "218765"
print"Original number: " , num
print "Next higher number: ", nextHighUsingAtMostOneSwap(num)
 
# This code is contributed by Nikita Tiwari.

// C# implementation to find the
// next higher number using atmost
// one swap operation
using System;
 
class GFG
{
 
// function to find the next
// higher number using atmost
// one swap operation
static String nextHighUsingAtMostOneSwap(String st)
{
    char[] num = st.ToCharArray();
    int l = num.Length;
     
    // to store the index of the
    // largest digit encountered
    // so far from the right
    int posRMax = l - 1;
     
    // to store the index of rightmost
    // digit which has a digit greater
    // to it on its right side
    int index = -1;
     
    // finding the 'index' of rightmost
    // digit which has a digit greater
    // to it on its right side
    for (int i = l - 2; i >= 0; i--)
    {
        if (num[i] >= num[posRMax])
            posRMax = i;
         
        // required digit found, store
        // its 'index' and break
        else
        {
            index = i;
            break;
        }
    }
     
    // if no such digit is found
    // which has a larger digit
    // on its right side
    if (index == -1)
        return "Not Possible";
     
    // to store the index of the
    // smallest digit greater than
    // the digit at 'index' and
    // right to it
    int greatSmallDgt = -1;
     
    // finding the index of the 
    // smallest digit greater
    // than the digit at 'index'
    // and right to it
    for (int i = l - 1; i > index; i--)
    {
        if (num[i] > num[index])
        {
            if (greatSmallDgt == -1)
                greatSmallDgt = i;
            else if (num[i] <= num[greatSmallDgt])
                greatSmallDgt = i;
        }
    }
     
    // swapping the digits
    char temp = num[index];
    num[index] = num[greatSmallDgt];
    num[greatSmallDgt] = temp;
     
    string res = new string(num);
     
    // required number
    return res;
}
 
// Driver Code
public static void Main()
{
    String num = "218765";
    Console.WriteLine("Original number: "
                                 + num );
    Console.WriteLine("Next higher number: "
         + nextHighUsingAtMostOneSwap(num));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation to
// find the next higher
// number using atmost
// one swap operation
 
// function to find the
// next higher number
// using atmost one swap
// operation
function nxtHighUsingAtMostOneSwap($num)
{
    $l = strlen($num);
     
    // to store the index of
    // the largest digit
    // encountered so far
    // from the right
    $posRMax = $l - 1;
     
    // to store the index of
    // rightmost digit which
    // has a digit greater to
    // it on its right side
    $index = -1;
     
    // finding the 'index' of
    // rightmost digit which
    // has a digit greater to
    // it on its right side
    for ($i = $l - 2; $i >= 0; $i--)
    {
        if ($num[$i] >= $num[$posRMax])
            $posRMax = $i;
         
        // required digit
        // found, store its
        // 'index' and break
        else
        {
            $index = $i;
            break;
        }
    }
     
    // if no such digit is
    // found which has a
    // larger digit on its
    // right side
    if ($index == -1)
        return "Not Possible";
     
    // to store the index of
    // the smallest digit
    // greater than the digit
    // at 'index' and right
    // to it
    $greatSmallDgt = -1;
     
    // finding the index of
    // the smallest digit
    // greater than the digit
    // at 'index' and right to it
    for ($i = $l - 1;
         $i > $index; $i--)
    {
        if ($num[$i] > $num[$index])
        {
            if ($greatSmallDgt == -1)
                $greatSmallDgt = $i;
            else if ($num[$i] <= $num[$greatSmallDgt])
                $greatSmallDgt = $i;
        }
    }
     
    // swapping the digits
    $temp = $num[$index];
    $num[$index] = $num[$greatSmallDgt];
    $num[$greatSmallDgt] = $temp;
     
    // required number
    return $num;
}
 
// Driver Code
$num = "218765";
echo "Original number: ".$num."\n";
echo "Next higher number: ".
      nxtHighUsingAtMostOneSwap($num);
 
// This code is contributed by mits
?>

<script>
 
// javascript implementation to find the next higher
// number using atmost one swap operation
 
     
// function to find the next higher number
// using atmost one swap operation
function nextHighUsingAtMostOneSwap(st)
{
    var num = st.split('');
    var l = num.length;
      
    // to store the index of the largest digit
    // encountered so far from the right
    var posRMax = l - 1;
      
    // to store the index of rightmost digit
    // which has a digit greater to it on its
    // right side
    var index = -1;
      
    // finding the 'index' of rightmost digit
    // which has a digit greater to it on its
    // right side
    for (var i = l - 2; i >= 0; i--)
    {
        if (num[i] >= num[posRMax])
            posRMax = i;
          
        // required digit found, store its
        // 'index' and break   
        else
        {
            index = i;
            break;
        }   
    }
      
    // if no such digit is found which has a
    // larger digit on its right side
    if (index == -1)
        return "Not Possible";
      
    // to store the index of the smallest digit
    // greater than the digit at 'index' and
    // right to it   
    var greatSmallDgt = -1;
      
    // finding the index of the smallest
    // digit greater than the digit at
    // 'index' and right to it   
    for (var i = l - 1; i > index; i--)   
    {
        if (num[i] > num[index])
        {
            if (greatSmallDgt == -1)
                greatSmallDgt = i;
            else if (num[i] <= num[greatSmallDgt])   
                greatSmallDgt = i;
        }
    }
      
    // swapping the digits
    var temp = num[index];
     num[index] = num[greatSmallDgt];
    num[greatSmallDgt] = temp;
      
    // required number
    return (num.join(''));
}
  
// Driver program to test above
var num = "218765";
document.write("Original number: "
                   + num );
document.write("<br>Next higher number: "
      + nextHighUsingAtMostOneSwap(num));
 
// This code contributed by shikhasingrajput
</script>

Original number: 218765
Next higher number: 258761

Complejidad de tiempo: O(n), donde n es el número de dígitos en num .

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.