Find the minimum permutation of A greater than B

0 0 6 minutes read

Given two numbers A and B, the task is to find the arrangement of digits of A such that it is just greater than the given number B, i.e., to find the minimum value permutation of A greater than B. If no such permutation is possible then print -1
Examples:

Input: A = 9236, B = 3125
Output: 3269
Explanation:
The minimum number greater than 3125 formed from the digits of A is 3269.
Input: A = 1234, B = 9879
Output: -1

Approach: The idea is to use next_permutation() and stol(). The following steps can be followed to compute the answer:

Take both the numbers as String input to make use of next_permutation().
Use stol() to find the long value of B.
Then find the lowest permutation of the number A.
For each permutation of A, check whether the number is greater than B.
If any permutation is greater than the number B then it is one of the possible answers. Select the minimum of all the possible answers.
If no such number is present print -1.

Below is the implementation of the above approach:

CPP

// C++ program to find the greater permutation
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 999999999999999999
 
// Function to find the greater permutation
ll solve(string a, string b)
{
    ll n, val, ans = inf;
 
    // Convert the string B to long
    val = stol(b);
    n = a.length();
 
    // To find the lowest permutation
    // of the number
    sort(a.begin(), a.end());
 
    // Find if the lowest permutation of A is
    // greater than the given number B
    if (stol(a) > val) {
        ans = min((ll)stol(a), ans);
    }
 
    // Find all the permutations of A
    while (next_permutation(a.begin(),
                            a.end())) {
        if (stol(a) > val) {
            ans = min((ll)stol(a), ans);
        }
    }
 
    // If ans is not the initial value
    // then return ans
    if (ans != inf) {
        return ans;
    }
    // Else return -1
    else {
        return -1;
    }
}
 
// Driver code
int main()
{
    string a, b;
    ll ans;
    a = "9236";
    b = "3145";
    ans = solve(a, b);
    cout << ans;
}

Java

// Java program to find the greater permutation
import java.util.*;
 
class GFG {
 
    private static ArrayList<String> _permutations
        = new ArrayList<String>();
 
    static long inf = 99999999;
 
    private static void GetPer(char[] list)
    {
        int x = list.length - 1;
        GetPer(list, 0, x);
    }
 
    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m) {
            _permutations.add(new String(list));
        }
        else
            for (int i = k; i <= m; i++) {
                char temp = list[k];
                list[k] = list[i];
                list[i] = temp;
 
                GetPer(list, k + 1, m);
 
                temp = list[k];
                list[k] = list[i];
                list[i] = temp;
            }
    }
 
    // Function to find the greater permutation
    static long solve(String a, String b)
    {
        long n, val, ans = inf;
 
        // Convert the string B to long
        val = Integer.valueOf(b);
        n = a.length();
 
        // To find the lowest permutation
        // of the number
        char[] a1 = a.toCharArray();
        Arrays.sort(a1);
        a = new String(a1);
 
        // Find if the lowest permutation of A is
        // greater than the given number B
        if (Integer.valueOf(a) > val) {
            ans = Math.min(Integer.valueOf(a), ans);
        }
 
        GetPer(a.toCharArray());
        // Find all the permutations of A
 
        for (String permut : _permutations) {
            if (Integer.valueOf(permut) > val) {
                ans = Math.min(Integer.valueOf(permut),
                               ans);
            }
        }
 
        // If ans is not the initial value
        // then return ans
        if (ans != inf) {
            return ans;
        }
        // Else return -1
        else {
            return -1;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String a, b;
        long ans;
        a = "9236";
        b = "3145";
        ans = solve(a, b);
        System.out.println(Long.valueOf(ans));
    }
}
 
// This code is contributed by phasing17

Python3

# Python program to find the greater permutation
from itertools import *
 
inf = 9999999999999
 
# Function to find the greater permutation
def solve(a, b):
    a = list(a)
    ans = inf;
 
    # Convert the string B to long
    val = int(b);
    n = len(a);
 
    # To find the lowest permutation
    # of the number
    a.sort()
 
    # Find if the lowest permutation of A is
    # greater than the given number B
    if (int("".join(a)) > val) :
        ans = min(int(a), ans);
     
 
    # Find all the permutations of A
    flag = False;
    permuts = list(permutations(a))
    for permut in permuts:
        curr = int("".join(permut))
         
        if (curr > val) :
            ans = min(curr, ans);
 
    # If ans is not the initial value
    # then return ans
    if (ans != inf):
        return ans;
     
    # Else return -1
    else:
        return -1;
     
# Driver code
a = "9236";
b = "3145";
ans = solve(a, b);
print(ans)
 
# This code is contributed by phasing17

C#

// C# program to find the greater permutation
 
using System;
using System.Collections.Generic;
 
class GFG {
    private static List<string> _permutations
        = new List<string>();
 
    static long inf = 99999999999999;
 
    private static void Swap(ref char a, ref char b)
    {
        if (a == b)
            return;
 
        a ^= b;
        b ^= a;
        a ^= b;
    }
 
    private static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }
 
    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m) {
            _permutations.Add(new string(list));
        }
        else
            for (int i = k; i <= m; i++) {
                Swap(ref list[k], ref list[i]);
                GetPer(list, k + 1, m);
                Swap(ref list[k], ref list[i]);
            }
    }
 
    // Function to find the greater permutation
    static long solve(string a, string b)
    {
        long n, val, ans = inf;
 
        // Convert the string B to long
        val = Convert.ToInt64(b);
        n = a.Length;
 
        // To find the lowest permutation
        // of the number
        char[] a1 = a.ToCharArray();
        Array.Sort(a1);
        a = new string(a1);
 
        // Find if the lowest permutation of A is
        // greater than the given number B
        if (Convert.ToInt64(a) > val) {
            ans = Math.Min(Convert.ToInt64(a), ans);
        }
 
        GetPer(a.ToCharArray());
        // Find all the permutations of A
 
        foreach(string permut in _permutations)
        {
            if (Convert.ToInt64(permut) > val) {
                ans = Math.Min(Convert.ToInt64(permut),
                               ans);
            }
        }
 
        // If ans is not the initial value
        // then return ans
        if (ans != inf) {
            return ans;
        }
        // Else return -1
        else {
            return -1;
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        string a, b;
        long ans;
        a = "9236";
        b = "3145";
        ans = solve(a, b);
        Console.WriteLine(ans);
    }
}
 
// This code is contributed by phasing17

Javascript

// JS program to find the greater permutation
 
let inf = 9999999999999
 
var nextPermutation = function(N) {
    const swap = (i, j) =>
        [N[i],N[j]] = [N[j],N[i]]
 
    let len = N.length - 1, i
    for (i = len - 1; N[i] >= N[i+1];) i--
    let j = i + 1, k = len
    while (j < k) swap(j++,k--)
    if (i >= 0) {
        for (j = i + 1; N[i] >= N[j];) j++
        swap(i,j)
    }
};
 
// Function to find the greater permutation
function solve(a, b)
{
    a = a.split("")
 
    let n, val, ans = inf;
 
    // Convert the string B to long
    val = parseInt(b);
    n = a.length;
 
    // To find the lowest permutation
    // of the number
    a.sort()
 
    // Find if the lowest permutation of A is
    // greater than the given number B
    if (parseInt(a) > val) {
        ans = Math.min(parseInt(a), ans);
    }
 
    // Find all the permutations of A
    a = a.map(function(item) {
    return parseInt(item);
});
 
    x = [...a];
    x.reverse();
     
    let flag = false;
    while (true)
    {
        nextPermutation(a);
         
        let curr = parseInt(a.join(""))
         
        if (curr > val) {
            ans = Math.min(curr, ans);
        }
         
         
        if (flag)
            break;
             
        if (a.join("") == x.join(""))
            flag = true;
    }
 
    // If ans is not the initial value
    // then return ans
    if (ans != inf) {
        return ans;
    }
    // Else return -1
    else {
        return -1;
    }
}
 
// Driver code
let a, b;
let ans;
a = "9236";
b = "3145";
ans = solve(a, b);
console.log(ans)
 
// This code is contributed by phasing17

Output:

Time Complexity:O(n * log n)

Space Complexity: O(1) as no extra space has been taken.

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!