Python program to solve the Exchange digits problem

July 2, 2020

Algorithm to solve the Exchange digits problem

Exchange digits problem

This Program was asked in TCS  CodeVita where we need to print the next greatest number from the combinations of the other number. Here is the Python program to solve the Exchange digits problem by finding all the combinations of numbers to get the next greatest number. The level of this problem is good and can solve the problem using an inbuilt function permutation.

 

All TCS CodeVita Questions with Answers

Problem Description

Compute the nearest larger number by interchanging its digits updated.Given 2 numbers a and b find the smallest number greater than b by interchanging the digits of a and if not possible print -1.

  • Input Format
    2 numbers a and b, separated by space.
  • Output Format
    A single number greater than b.

    If not possible, print -1

  • Constraints

    1 <= a,b <= 10000000

Example 1:

Sample Input:

    459 500

Sample Output:
    549

Example 2:

Sample Input:

    645757 457765

Sample Output:
    465577

 

Algorithm

  • Step 1:- Start.
  • Step 2:- From itertools import permutation function.
  • Step 3:- Take user inputs.
  • Step 4:- Initialize a flag variable to 0[zero].
  • Step 5:- Convert number1 to String and then to a list.
  • Step 6:- Sort the list by using the sorted function.
  • Step 7:- Initialize a perm variable that stores the permutations of the list.
  • Step 8:- Iterate through the perm variable by converting it to the list.
  • Step 9:- Initialize an empty string.
  • Step 10:- Concatenate all the iterators to a string variable.
  • Step 11:- Typecast the string variable to an integer to check the next greatest number.
  • Step 12:- Continue the process until if condition gets the True value.
  • Step 13:- As the if condition gets the true value, chang the flag variable to 1 and break the loop.
  • Step 14:- Check the flag whether we got the greatest value or not.
  • Step 15:- Print the string variable if flag is 1 else print -1.
  • Step 16:- End.

Python program to solve the Exchange digits problem

#import itertools to get permutation function
from itertools import permutations
#take inputs
num1 = int(input('Enter the 1st number :'))
num2 = int(input('Enter the 2nd number :'))
#initialize a flag variable
flag = 0
#convert num1 to string list
num1 = list(str(num1))
#sort the list
num1 = sorted(num1)
#find all permutations
perm = permutations(num1) 
#iterate through all permutations 
for i in list(perm): 
    #initialize an string
    string = " "
    #iterate through an string
    for j in i:
        string+=j
    #typecast string to integer
    #check for next greater value
    if int(string) > num2:
        #if True Change the flag variable 
        #break the loop
        flag = 1
        break
#check if the number is found or not
if flag == 1:
    print(string)
else:
    print(-1)
Output:
Enter the 1st number :459
Enter the 2nd number :500
549

Staircase Problem in Other Coding Languages

C

Please contribute your code for For Solution of Exchange digit problem in C programing we will post it soon on the web site

 

C++

Please contribute your code for For Solution of Exchange digit problem in C++ programing we will post it soon on the web site

 

Java

Please contribute your code for For Solution of Exchange digit problem in Java programing we will post it soon on the web site

 

11 comments on “Python program to solve the Exchange digits problem”


  • shubhamborkar512

    ## Solution using java

    public class Solution {
    static int res;

    public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    res = Integer.MAX_VALUE;
    List list = new ArrayList();
    while (a > 0) {
    list.add(a % 10);
    a /= 10;
    }

    backtrack(0, b, list, 0, new boolean[list.size()]);

    System.out.println(res == b ? -1 : res);
    }

    private static void backtrack(int count, int b, List list, int num, boolean[] visited) {

    if (count == list.size()) {
    if (num > b) {
    res = Math.min(res, num);
    }
    return;
    }

    for (int i = 0; i < list.size(); i++) {
    if (!visited[i]) {
    visited[i] = true;
    backtrack(count + 1, b, list, num * 10 + list.get(i), visited);
    visited[i] = false;
    }
    }

    }
    }

    0

  • Abhisek

    #without using permutation

    def arrange_digits(n,t):

    d_list = list(map(int,list(str(n))))
    d_list.sort()
    output = “”

    for i in range(len(str(t))-1):

    has_found = False

    for j in range(len(d_list)):

    if str(d_list[j])==str(t)[i]:
    remain = “”
    temp_arr = d_list.copy()
    temp_arr.pop(j)

    for r in temp_arr[::-1]:
    remain += str(r)

    if remain>str(t)[i+1::1]:
    output += str(d_list.pop(j))
    has_found = True
    break
    else:
    continue

    elif d_list[j]>int(str(t)[i]):
    output += str(d_list.pop(j))
    for d in d_list[::1]:
    output += str(d)

    return int(output)

    if has_found:
    has_found = False
    else:
    return -1

    return int(output)

    number,target = map(int,input().split())

    print(arrange_digits(number,target))

    0

  • RISHAV

    from itertools import permutations
    m = input()
    n = input()
    lst = sorted([int(“”.join(char)) for char in permutations(m)])
    for i in lst:
    if i > int(n):
    print(i)
    break

    0

  • Vicky

    from itertools import permutations
    a1,a2=input().split()
    a=permutations(a1)
    list1=[]
    for i in a:
    list1.append(int(“”.join(i)))
    min1=1000000000
    for i in range(len(list1)):
    if(list1[i]>int(a2)):
    if(list1[i]<min1):
    min1=list1[i]
    if(min1==1000000000):
    print("-1")
    else:
    print(min1)

    0

  • Prabha

    x,y=input().split()
    from itertools import permutations as pm
    a=list(pm(x))
    l=sorted(list(map(”.join,a)))
    for i in l:
    if i>y:
    break
    print(i)

    1

  • Paras

    C++ Solution
    #include
    using namespace std;
    int fac(int n)
    {
    if(n==0 || n==1)
    return 1;
    else
    return n*fac(n-1);
    }
    int main()
    {
    int a,b;
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()>s2.size())
    {
    sort(s1.begin(),s1.end());
    cout<<s1;
    }
    else if(s1.size()<s2.size())
    {
    cout<<"-1";
    }
    else
    {
    int i,j,k;
    vector A;
    for(i=0;i<fac(s1.size());i++)
    {
    next_permutation(s1.begin(),s1.end());;
    A.push_back(s1);
    }
    sort(A.begin(),A.end());
    stringstream ss1;
    int b;
    ss1<>b;
    for(i=0;i<A.size();i++)
    {
    stringstream ss;
    ss<>s;
    if(s>b)
    {
    cout<<A[i];
    break;
    }
    }
    }

    }

    0

  • Shivam

    n=int(input())
    m=int(input())
    grt_ele=[]
    n=list(str(n))
    perm=list(permutations(n))
    res = list(map(“”.join, perm))
    for i in res:
    if int(m)<int(i):
    grt_ele.append(i)
    print(min(grt_ele))

    1