Q:

# Number following the pattern

Problem statement:

Given a pattern containing only I's and D's'I' stands for increasing and 'D' for decreasing. Devise an algorithm to print the minimum number following that pattern. Digits are from 1-9 and digits can't repeat.

Example:

```    Input:
IIDDIDD

Output:
12543876```

### All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Solution

The pattern & number to be generated

1. Length of minimum number = string length+1
Hence, maximum string length possible is 8, since we can construct only with different digits (1-9)
2. 'I' means the next digit will be 1 greater than the current & 'D' means the next digit will be 1 less than the current digit
"II" → 123
"DD" → 321

The problem can be used with help of stack. The concept is to create stack with consecutive number same as depth of a local contiguous sequence of 'D'.

Prerequisite:

1. Input pattern, string s
2. Stack st to store the digits
```    Function findMinFromPattern(string s)
1.  Declare a stack st;
2.  FOR i=0 : pattern length
EnQueue (st, i+1); //push i+1 at first, i+1 becuase i is 0-indexed
IF (entire pattern is processed || s[i] =='I')
While(stack is not empty){
Pop and print
End While
END IF
END FOR
END FUNCTION```

``````#include <bits/stdc++.h>
using namespace std;

void findMinFromPattern(string s){
stack<int> st; //stack declared using STL
for(int i=0;i<=s.length();i++){
//push i+1 at first, i+1 becuase i is 0-indexed
st.push(i+1);
//when string length is processed or pattern in I
if(s.length()==i || s[i]=='I' ){
//pop and print until stack is empty
while(!st.empty()){
cout<<st.top();
st.pop();
}
}
}
cout<<endl;
}

int main(){
cout<<"enter pattern\n";
string s;
cin>>s;

if(s.length()>8){
cout<<"Not possible,length>8\n";
}
else{
cout<<"The minimum number generated is:\n";
findMinFromPattern(s);//function to print
}
return 0;
}
``````

Output

```First run:
enter pattern
IIDDIDD
The minimum number generated is:
12543876

Second run:
enter pattern
IIIIIIIIDDDDIII
Not possible,length>8```

Example with explanation:

```Pattern string:
IIDDIDD

0 th iteration
i=0
EnQueue(st,i+1)
Stack status:
1
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
1
Output up to now:
1
Stack status;
Empty stack
-------------------------------------------------------------

1st iteration
i=1
EnQueue(st,i+1)
Stack status:
2
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
2
Output up to now:
12
Stack status;
Empty stack
-------------------------------------------------------------

2nd iteration
i=2
EnQueue(st,i+1)
Stack status:
3
S[i]=='D'
Nothing to do
Output up to now:
12
Stack status;
3
-------------------------------------------------------------

3rd iteration
i=3
EnQueue(st,i+1)
Stack status:
3
4(top)
S[i]=='D'
Nothing to do
Output up to now:
12
Stack status;
3
4(top)
-------------------------------------------------------------

4th iteration
i=4
EnQueue(st,i+1)
Stack status:
3
4
5(top)
S[i]=='I'
So pop and print until stack becomes empty
Thus printing:
5, then 4,then 3
Output up to now:
12543
Stack status;
Empty stack
-------------------------------------------------------------

5th iteration
i=5
EnQueue(st,i+1)
Stack status:
6
S[i]=='D'
Nothing to do
Output up to now:
12543
Stack status;
6
-------------------------------------------------------------

6th iteration
i=6
EnQueue(st,i+1)
Stack status:
6
7(top)
S[i]=='D'
Nothing to do
Output up to now:
12543
-------------------------------------------------------------

7th iteration
i=7
EnQueue(st,i+1)
Stack status:
6
7
8(top)
Entire string is processed
Pop and print until stack becomes empty
Print:
8, then 7, then 6
Output up to now:
12543876
Exit:
Minimum no is:
12543876```

need an explanation for this answer? contact us directly to get an explanation for this answer
need an explanation for this answer? contact us directly to get an explanation for this answer

test answer for test notification

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (2)