Given a non-negative number num. The problem is to find the smallest number greater than num by performing atmost on swap operation between any two digits in num. If no larger number can be formed then print “Not Possible”.
The number could be very large and may not even fit into long long int.
Examples:
Input : num = “218765”
Output : 258761
Explanation: We swap 5 and 1 to get the smallest number greater than ‘num’Input : num = “541322”
Output : 542312
Approach: First find the index of the rightmost digit which has a digit larger than it and is on the right side to it. Let its index be ind. Now, find the index of the smallest digit greater than the digit at index ind and is right to it. Let its index be greatSmallDgt. Finally swap the digits at the indexes ind and greatSmallDgt. If the digits of num are in decreasing order then print “Not Possible”.
Implementation:
C++
// 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 operationstring 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 aboveint main(){ string num = "218765"; cout << "Original number: " << num << endl; cout << "Next higher number: " << nxtHighUsingAtMostOneSwap(num); return 0;} |
Java
// JAVA implementation to find the next higher// number using atmost one swap operationimport java.io.*;public 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
# Python implementation to find the next higher# number using atmost one swap operation# function to find the next higher number# using atmost one swap operationdef 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 elif (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 abovenum = "218765"print"Original number: " , num print "Next higher number: ", nextHighUsingAtMostOneSwap(num)# This code is contributed by Nikita Tiwari. |
C#
// C# implementation to find the // next higher number using atmost// one swap operationusing System;class GFG{// function to find the next // higher number using atmost // one swap operationstatic 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 Codepublic 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// PHP implementation to // find the next higher // number using atmost// one swap operation// function to find the // next higher number// using atmost one swap// operationfunction 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?> |
Javascript
<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 operationfunction 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 abovevar num = "218765";document.write("Original number: " + num );document.write("<br>Next higher number: " + nextHighUsingAtMostOneSwap(num));// This code contributed by shikhasingrajput </script> |
Output
Original number: 218765 Next higher number: 258761
Time Complexity: O(n), where n is the number of digits in num.
Auxiliary Space: O(1)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
