# 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 increasing3. 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 -> 21i -> 12ddd -> 4321iii -> 1234dddiddd -> 43218765iiddd -> 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 <= 8str 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

• Related Topics

Run

Run
Id Name