Smallest Number Following Pattern
1. You are given a pattern of upto 8 length containing characters 'i' and 'd'.Input Format
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 is managed for youOutput Format
Smallest sequence of digits (from 1 to 9) without duplicacy and following the patternQuestion Video
0 < str.length <= 8Sample Input
str contains only 'd' and 'i'
ddddiiiiSample 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