Given a non-negative number num. The problem is to apply at most one swap operation on the number num so that the resultant is the largest possible number. The number could be very large so a string type can be used to store the number.
Examples:
Input : n = 8725634 Output : 8765234 Swapped the digits 2 and 6. Input : n = 54321 Output : 54321 No swapping of digits required.
Create an array rightMax[]. rightMax[i] contains the index of the greatest digit which is on the right side of num[i] and also greater than num[i]. If no such digit exists then rightMax[i] = -1. Now, traverse the rightMax[] array from i = 0 to n-1(where n is the total number of digits in num), and find the first element having rightMax[i] != -1. Perform the swap(num[i], num[rightMax[i]]) operation and break.
C++
// C++ implementation to form the largest number// by applying atmost one swap operation#include <bits/stdc++.h>using namespace std;// function to form the largest number by// applying atmost one swap operationstring largestNumber(string num){ int n = num.size(); int rightMax[n], right; // for the rightmost digit, there // will be no greater right digit rightMax[n - 1] = -1; // index of the greatest right digit till the // current index from the right direction right = n - 1; // traverse the array from second right element // up to the left element for (int i = n - 2; i >= 0; i--) { // if 'num[i]' is less than the greatest digit // encountered so far if (num[i] < num[right]) rightMax[i] = right; // else else { // there is no greater right digit // for 'num[i]' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from left to right for (int i = 0; i < n; i++) { // if for the current digit, greater right digit exists // then swap it with its greater right digit and break if (rightMax[i] != -1) { // performing the required swap operation swap(num[i], num[rightMax[i]]); break; } } // required largest number return num;}// Driver program to test aboveint main(){ string num = "8725634"; cout << "Largest number:" << largestNumber(num); return 0;} |
Java
//Java implementation to form the largest number//by applying atmost one swap operationpublic class GFG{ // function to form the largest number by // applying atmost one swap operation static String largestNumber(String num) { int n = num.length(); int right; int rightMax[] = new int[n]; // for the rightmost digit, there // will be no greater right digit rightMax[n - 1] = -1; // index of the greatest right digit // till the current index from the // right direction right = n - 1; // traverse the array from second right // element up to the left element for (int i = n - 1; i >= 0 ; i--) { // if 'num.charAt(i)' is less than the // greatest digit encountered so far if (num.charAt(i) < num.charAt(right)) rightMax[i] = right; else { // there is no greater right digit // for 'num.charAt(i)' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from // left to right for (int i = 0; i < n; i++) { // if for the current digit, greater // right digit exists then swap it // with its greater right digit and break if (rightMax[i] != -1) { // performing the required swap operation num = swap(num,i,rightMax[i]); break; } } // required largest number return num; } // Utility method to swap two characters // in a String static String swap(String num, int i, int j) { StringBuilder sb= new StringBuilder(num); sb.setCharAt(i, num.charAt(j)); sb.setCharAt(j, num.charAt(i)); return sb.toString(); } //Driver Function to test above Function public static void main(String[] args) { String num = "8725634"; System.out.println("Largest Number : " + largestNumber(num)); }}//This code is contributed by Sumit Ghosh |
Python3
# Python implementation to form the largest number# by applying atmost one swap operation# function to form the largest number by# applying atmost one swap operationdef largestNumber(num): n = len(num) rightMax = [0 for i in range(n)] # for the rightmost digit, there # will be no greater right digit rightMax[n - 1] = -1 # index of the greatest right digit till the # current index from the right direction right = n - 1 # traverse the array from second right element # up to the left element i = n - 2 while i >= 0: # if 'num[i]' is less than the greatest digit # encountered so far if (num[i] < num[right]): rightMax[i] = right # else else: # there is no greater right digit # for 'num[i]' rightMax[i] = -1 # update 'right' index right = i i -= 1 # traverse the 'rightMax[]' array from left to right for i in range(n): # if for the current digit, greater right digit exists # then swap it with its greater right digit and break if (rightMax[i] != -1): # performing the required swap operation t = num[i] num[i] = num[rightMax[i]] num[rightMax[i]] = t break # required largest number return num # Driver program to test abovenum = "8725634"li = [i for i in num]print("Largest number: ")li = largestNumber(li)for i in li: print(i,end=" ")print()#This code is contributed by Sachin Bisht |
C#
// C# implementation to form the largest number// by applying atmost one swap operationusing System;using System.Text;public class GFG{ // function to form the largest number by // applying atmost one swap operation static String largestNumber(String num) { int n = num.Length; int right; int[] rightMax = new int[n]; // for the rightmost digit, there // will be no greater right digit rightMax[n - 1] = -1; // index of the greatest right digit // till the current index from the // right direction right = n - 1; // traverse the array from second right // element up to the left element for (int i = n - 1; i >= 0 ; i--) { // if 'num.charAt(i)' is less than the // greatest digit encountered so far if (num[i] < num[right]) rightMax[i] = right; else { // there is no greater right digit // for 'num.charAt(i)' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from // left to right for (int i = 0; i < n; i++) { // if for the current digit, greater // right digit exists then swap it // with its greater right digit and break if (rightMax[i] != -1) { // performing the required swap operation num = swap(num,i,rightMax[i]); break; } } // required largest number return num; } // Utility method to swap two characters // in a String static String swap(String num, int i, int j) { StringBuilder sb= new StringBuilder(num); sb[i]=num[j]; sb[j]=num[i]; return sb.ToString(); } //Driver Function to test above Function public static void Main() { String num = "8725634"; Console.WriteLine("Largest Number : " +largestNumber(num)); }}//This code is contributed by mits |
PHP
<?php// PHP implementation to form the // largest number by applying atmost// one swap operation // function to form the largest number by // applying atmost one swap operation function largestNumber($num) { $n = strlen($num); $rightMax[$n] = array(0); $right; // for the rightmost digit, there // will be no greater right digit $rightMax[$n - 1] = -1; // index of the greatest right // digit till the current index // from the right direction $right = $n - 1; // traverse the array from second // right element up to the left element for ($i = $n - 2; $i >= 0; $i--) { // if 'num[i]' is less than the // greatest digit encountered so far if ($num[$i] < $num[$right]) $rightMax[$i] = $right; // else else { // there is no greater right // digit for 'num[i]' $rightMax[$i] = -1; // update 'right' index $right = $i; } } // traverse the 'rightMax[]' // array from left to right for ($i = 0; $i < $n; $i++) { // if for the current digit, greater // right digit exists then swap it // with its greater right digit and break if ($rightMax[$i] != -1) { // performing the required swap operation list($num[$i], $num[$rightMax[$i]]) = array($num[$rightMax[$i]], $num[$i]); break; } } // required largest number return $num; } // Driver Code$num = "8725634"; echo "Largest number: ", largestNumber($num); // This code is contributed by jit_t?> |
Javascript
<script>// Javascript implementation to form the largest number// by applying atmost one swap operation// function to form the largest number by// applying atmost one swap operationfunction largestNumber(num){ var n = num.length; var rightMax = Array(n), right; // for the rightmost digit, there // will be no greater right digit rightMax[n - 1] = -1; // index of the greatest right digit till the // current index from the right direction right = n - 1; // traverse the array from second right element // up to the left element for (var i = n - 2; i >= 0; i--) { // if 'num[i]' is less than the greatest digit // encountered so far if (num[i] < num[right]) rightMax[i] = right; // else else { // there is no greater right digit // for 'num[i]' rightMax[i] = -1; // update 'right' index right = i; } } // traverse the 'rightMax[]' array from left to right for (var i = 0; i < n; i++) { // if for the current digit, greater right digit exists // then swap it with its greater right digit and break if (rightMax[i] != -1) { // performing the required swap operation var tmp = num[i]; num[i] = num[rightMax[i]]; num[rightMax[i]] = tmp break; } } // required largest number return num.join('');}// Driver program to test abovevar num = "8725634".split('');document.write( "Largest number:" + largestNumber(num));// This code is contributed by rrrtnx.</script> |
Output:
Largest number: 8765234
Time Complexity: O(n), where n is the total number of digits.
Auxiliary Space: O(n), where n is the total number of digits.
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.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
