Given Two Numbers N and K ,Find rearrangement of N such that digits of K does not appear as a sub sequence in N

Problem Statement 

You are Given two numbers N and K where K is less than N and digits of K is either in increasing order or same as its previous digit.You have to rearrange digits of N in such a manner such that digits of K does not appear as a subsequence in it.If it is impossible print -1.Multiple output is possible.

Constraints-1≤N≤10^100,1≤K≤10^8

input: N=93039373637 

 K=339 

Ouput: 97093736333 

 Input:N=965

 K=55  

Output: 965 

 Input :N=7564233 

K=33  

Output: -1

Approach: As given in the question the digits of K will be either same as its previous digit or greater than its previous digit but not less than its previous digit this gives us an great clue that if somehow we place greater digit prior to smaller digit in N then obtaining K as sub sequence is not possible .One great way to do this is to sort the digits of N in decreasing order.But if K contains only 1 distinct digit then it is impossible to make such rearrangement,so in this case output will be -1.

Solution

Below is the java implementation of above approach

Code:

import java.io.*;

class Solution {
    public static void main(String[] args) {
        Scanner obj=new Scanner(System.in);
        String n=obj.next();      // Taking input of Integer N as String
        String k=obj.next();      // Taking input of Integer K as String
        
        HashMap<Character,Integer> map1=new HashMap<>();  //Creating map1 for frequency of digits in N
        HashMap<Character,Integer> map2=new HashMap<>();  //Creating map2 for frequency of digits in k
        
        //Creating digit frequency map of N
        for(int i=0;i<n.length();i++)
        {
            Integer m=map1.get(n.charAt(i));
            map1.put(n.charAt(i), (m==null)?1:m+1);
        }
        
        // Creating Digit Frequency map of K
        for(int i=0;i<k.length();i++)
        {
            Integer m=map2.get(k.charAt(i));
            map2.put(k.charAt(i), (m==null)?1:m+1);
        }
        
        //Check if there are at least same or greater frequency of a particular digit of K in N
              
        boolean flag=true;
        for(Map.Entry<Character, Integer> e:map2.entrySet())
        {
            if(map1.getOrDefault(e.getKey(), 0)<e.getValue())
            {
                flag=false;
                break;
            }
        }
        if(!flag)
        {
            // if there is not same number of particular digit in N then output N
            System.out.println(n);
        }
        else
        {
            //Creating set to check if there is only one distinct digit in K
            HashSet<Character> set=new HashSet<>();
            for(int i=0;i<k.length();i++)
            {
                set.add(k.charAt(i));
            }
            if(set.size()==1)
            {
                // if only one distinct digit is present then answer will always be -1
                System.out.println("-1");
            }
            else
            {
                // Sort and print N in reverse order
                System.out.println(rearrange(n));
            }
        }
        obj.close();
    }
      public static String rearrange(String n)
    {
        StringBuilder sb=new StringBuilder();
        char[] stringArray=n.toCharArray(); //converting to char Array
        Arrays.sort(stringArray);          // sorting Array
        for(int i=stringArray.length-1;i>=0;i--)
        {
            sb.append(stringArray[i]);   // appending in reverse order
        }
        return sb.toString();    // returning the string
    }
}

if len=length of N,then

Time complexity=O(len*log(len))

Feel free to comment if you have any doubts in comment section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here