Redirecting to
NADOS

Smallest Number Following Pattern

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a pattern of upto 8 length containing characters 'i' and 'd'.
2. 'd' stands for decreasing and 'i' stands for increasing
3. You have to print the smallest number, using the digits 1 to 9 only without repetition, such that
the digit decreases following a d and increases follwing an i.

e.g.
d -> 21
i -> 12
ddd -> 4321
iii -> 1234
dddiddd -> 43218765
iiddd -> 126543
Input Format
Input is managed for you
Output Format
Smallest sequence of digits (from 1 to 9) without duplicacy and following the pattern
Question Video
Constraints
0 < str.length <= 8
str contains only 'd' and 'i'
Sample Input
ddddiiii
Sample Output
543216789


  • Editorial

    Let us first understand some of the pattern through examples:

    Example1- only d ->  2 d 1 our answer would be 21 and we can clearly see that 2 is decreasing to 1.

    Example2- only I ->   1 i 2 our answer would be 12, 1 increasing to 2 and 11 because 11 has repetition digit 1 and that is against the rules.

    Example3- iii ->  1 i 2 i 3 i 4 so our answer is 1234 where 1<2<3<4 are in increasing order and this is the smallest number for this particular pattern.

    Example4- ddd ->  4 d 3 d 2 d 1 our output here is 4321 which is in decreasing order and is the smallest number for this particular pattern.

    Example5- ddidd -> 3 d 2 d 1 i 6 d 5 d 4 our output here is 321654 as we can see all the rules are followed where 3>2>1<6>5>4 and this is the smallest number for this pattern because if we analyze then according t first dd the smallest decreasing number is 321 and for second dd it is 654 as repetition is not allowed and i is splitting the two ds .

    This thing will work and will provide us the smallest number for any particular pattern because the most significant place has the smallest numbers followed by other places with no repetition.

    Also when we increase we have to check the sequence of ds and then the least possible increment is done whereas while decreasing we always decrease by 1.

    Algorithm:

    1. Whenever we come across d we will push the number into the stack and then we will increment the number by 1.

    2. When we get i in the pattern we will first push into the stack then we will increment the number and then we will pop from the stack will the stack is empty and will print the result.

    3. When we reach the end of the pattern we will push the last increment number into the stack and then will pop from the stack till it is empty and will print the result.

    Let us take an example-

    Pattern: ddidddid

    Now we will pop as we reached I and we will print 3 2 1

    Now we will pop as we reached I and we will print 7654

    As we discussed above we reached end of pattern so last num will be pushed into the stack.

    Now we will pop from the stack till it is empty and will print 98

    So our final smallest number for this pattern is 321765498.

    Stack < Integer > st = new Stack<>();
                                    num=1;
                                    for(int i=0;i < arr.length;i++)
                                    {
                                     char ch = arr.charAt(i);
                                     if(ch == 'd'){                               //when we encounter d
                                       st.push(num);
                                       num++;
                                     }else{                                         // when we encounter i
                                       st.push(num);
                                       num++;
                                       while(st.size() > 0){
                                          System.out.print(st.pop());
                                        } 
                                     }
                                    }
                                     st.push(num);                               // for last number
                                     while(st.size() > 0){
                                          System.out.print(st.pop());
                                        }

    java false

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name