Form the largest number using at most one swap operation | C ++ implementation to form the largest number by applying atmost one swap operation ; function to form the largest number by applying atmost one swap operation ; for the rightmost digit , there will be no greater right digit ; index of the greatest right digit till the current index from the right direction ; traverse the array from second right element up to the left element ; if ' num [ i ] ' is less than the greatest digit encountered so far ; else ; there is no greater right digit for ' num [ i ] ' ; update ' right ' index ; traverse the ' rightMax [ ] ' array from left to right ; if for the current digit , greater right digit exists then swap it with its greater right digit and break ; performing the required swap operation ; required largest number ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; string largestNumber ( string num ) { int n = num . size ( ) ; int rightMax [ n ] , right ; rightMax [ n - 1 ] = -1 ; right = n - 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( num [ i ] < num [ right ] ) rightMax [ i ] = right ; else { rightMax [ i ] = -1 ; right = i ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( rightMax [ i ] != -1 ) { swap ( num [ i ] , num [ rightMax [ i ] ] ) ; break ; } } return num ; } int main ( ) { string num = "8725634" ; cout << " Largest ▁ number : " << largestNumber ( num ) ; return 0 ; }