Nearest greater number by interchanging the digits

0 0 5 minutes read

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 code
int 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 value
import 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 value
min1 = 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 code
A = 213
B = 111
 
# Convert integer value into to
# find all the permutation of the number
str2 = 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 exists
if _count == 1:
    print(h)
else:
    print(-1)
 
# This code is contributed by
# mohit

C#

// C# program to find nearest greater value
using 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 value
 
let 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 character
function 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 code
let 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:

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 zambiatek!