Given two integers A and B. The task is to find the nearest greater value to B by interchanging the digits of A. If no such permutation possible then print -1.
Examples:
Input: A = 459, B = 500
Output: 549
549 is the nearest greater.
Input: A = 321, B = 567
Output: -1
Input: A = 231, B = 125
Output: 132
Prerequisites: All permutations of a string
Approach:
- Set the minimum value of min1 by using the Integer.MAX_VALUE
- Interchange the digit of A by using above mentioned permutation method.
- Check if the permutation of A is less than min1 or not. If less then update min1 as A.
- Repeat this for all permutations of A and find the minimum greater value
Below is the implementation of the above approach :
C++
// C++ program to find nearest greater value#include <bits/stdc++.h>using namespace std;int min1 = INT_MAX;int _count = 0;// Find all the possible permutation of Value A.int permutation(string str1, int i, int n, int p){ if (i == n) { // Convert into Integer int q = stoi(str1); // Find the minimum value of A by interchanging // the digit of A and store min1. if (q - p > 0 && q < min1) { min1 = q; _count = 1; } } else { for (int j = i; j <= n; j++) { // Swap two string character swap(str1[i], str1[j]); permutation(str1, i + 1, n, p); swap(str1[i], str1[j]); } } return min1;}// Driver codeint main(){ int A = 213; int B = 111; // Convert integer value into string to // find all the permutation of the number string str1 = to_string(A); int len = str1.length(); int h = permutation(str1, 0, len - 1, B); // count=1 means number greater than B exists _count ? cout << h << endl : cout << -1 << endl; return 0;}// This code is contributed by// sanjeev2552 |
Java
// JAVA program to find nearest greater valueimport java.io.*;import java.util.*;class GFG { static int min1 = Integer.MAX_VALUE; static int count = 0; // Find all the possible permutation of Value A. public int permutation(String str1, int i, int n, int p) { if (i == n) { // Convert into Integer int q = Integer.parseInt(str1); // Find the minimum value of A by interchanging // the digit of A and store min1. if (q - p > 0 && q < min1) { min1 = q; count = 1; } } else { for (int j = i; j <= n; j++) { str1 = swap(str1, i, j); permutation(str1, i + 1, n, p); str1 = swap(str1, i, j); } } return min1; } // Swap two string character public String swap(String str, int i, int j) { char ch[] = str.toCharArray(); char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; // Return the string after // swapping between two character. return String.valueOf(ch); } // Driver code public static void main(String[] args) { int A = 213; int B = 111; GFG gfg = new GFG(); // Convert integer value into string to // find all the permutation of the number String str1 = Integer.toString(A); int len = str1.length(); int h = gfg.permutation(str1, 0, len - 1, B); // count=1 means number greater than B exists if (count == 1) System.out.println(h); else System.out.println(-1); }} |
Python3
# Python3 program to find nearest greater valuemin1 = 10**9_count = 0# Find all the possible permutation of Value A.def permutation(str1, i, n, p): global min1, _count if (i == n): # Convert into Integer str1 = "".join(str1) q = int(str1) # Find the minimum value of A # by interchanging the digits # of A and store min1. if (q - p > 0 and q < min1): min1 = q _count = 1 else: for j in range(i, n + 1): # Swap two character) str1[i], str1[j] = str1[j], str1[i] permutation(str1, i + 1, n, p) str1[i], str1[j] = str1[j], str1[i] return min1# Driver codeA = 213B = 111# Convert integer value into to# find all the permutation of the numberstr2 = str(A)str1 = [i for i in str2]le = len(str1)h = permutation(str1, 0, le - 1, B)# count=1 means number greater than B existsif _count == 1: print(h)else: print(-1)# This code is contributed by# mohit |
C#
// C# program to find nearest greater valueusing System; class GFG{ static int min1 = int.MaxValue; static int count = 0; // Find all the possible permutation of Value A. public int permutation(String str1, int i, int n, int p) { if (i == n) { // Convert into Integer int q = int.Parse(str1); // Find the minimum value of A by interchanging // the digit of A and store min1. if (q - p > 0 && q < min1) { min1 = q; count = 1; } } else { for (int j = i; j <= n; j++) { str1 = swap(str1, i, j); permutation(str1, i + 1, n, p); str1 = swap(str1, i, j); } } return min1; } // Swap two string character public String swap(String str, int i, int j) { char []ch = str.ToCharArray(); char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; // Return the string after // swapping between two character. return String.Join("", ch); } // Driver code public static void Main(String[] args) { int A = 213; int B = 111; GFG gfg = new GFG(); // Convert integer value into string to // find all the permutation of the number String str1 = A.ToString(); int len = str1.Length; int h = gfg.permutation(str1, 0, len - 1, B); // count=1 means number greater than B exists if (count == 1) Console.WriteLine(h); else Console.WriteLine(-1); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JAVAscript program to find nearest greater valuelet min1 = Number.MAX_VALUE;let count = 0;// Find all the possible permutation of Value A.function permutation(str1,i,n,p){ if (i == n) { // Convert into Integer let q = parseInt(str1); // Find the minimum value of A by interchanging // the digit of A and store min1. if (q - p > 0 && q < min1) { min1 = q; count = 1; } } else { for (let j = i; j <= n; j++) { str1 = swap(str1, i, j); permutation(str1, i + 1, n, p); str1 = swap(str1, i, j); } } return min1;} // Swap two string characterfunction swap(str,i,j){ let ch = str.split(""); let temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; // Return the string after // swapping between two character. return (ch).join("");}// Driver codelet A = 213; let B = 111; // Convert integer value into string to // find all the permutation of the number let str1 = A.toString(); let len = str1.length; let h = permutation(str1, 0, len - 1, B); // count=1 means number greater than B exists if (count == 1) document.write(h); else document.write(-1);// This code is contributed by unknown2108</script> |
Output:
123
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!
