# Find minimum number from a ID sequence

The problem is to find the minimum number from a given ID sequence. The ID sequence consists of the letters "I" and "D," where "I" stands for increasing and "D" stands for decreasing. The goal is to construct a sequence of consecutive numbers such that each "I" indicates an increasing subsequence, and each "D" indicates a decreasing subsequence.

## Problem Statement

Given an ID sequence, we need to construct a sequence of consecutive numbers that satisfies the increasing and decreasing conditions specified by the ID sequence.

## Example

Consider the following examples:

1. Input: "DDIIIDI" Output: "32145768"

2. Input: "IDD" Output: "1432"

3. Input: "IIDDI" Output: "125436"

## Idea to Solve the Problem

To construct the sequence of consecutive numbers from the ID sequence, we can use a stack to keep track of the numbers. We initialize a tracker stack with consecutive numbers starting from 1. Then, for each character in the ID sequence, we perform the following steps:

1. Push the current number (starting from 1) onto the tracker stack.
2. If the current character is "I," it means we need to start an increasing subsequence. We continue pushing consecutive numbers onto the tracker stack until we encounter a "D" or reach the end of the ID sequence.
3. If the current character is "D," it means we need to start a decreasing subsequence. We pop numbers from the tracker stack and append them to the result string until we encounter an "I" or the tracker stack becomes empty.

## Pseudocode

``````Function minimumNumber(sequence):
n = length of sequence
result = ""

if n > 0:
Create an empty stack tracker

for i from 0 to n:
Push (i + 1) onto tracker
if i == n or sequence[i] == 'I':
while tracker is not empty:
Append tracker.peek() to result
Pop the top element from tracker

Display "Given sequence: " + sequence
Display "Result: " + result
``````

## Algorithm

1. Create a class called `Decode`.
2. Define a function called `minimumNumber` that takes the input sequence as a parameter.
3. Get the length of the sequence `n`.
4. Initialize an empty string called `result` to store the final sequence.
5. If the sequence is not empty, create an empty stack called `tracker`.
6. Iterate through the sequence from index 0 to n - 1 using a loop.
7. Push the number (i + 1) onto the stack `tracker`.
8. If the current character is "I" or the end of the sequence is reached: a. While the stack `tracker` is not empty, do the following: i. Append the top element of the stack `tracker` to the string `result`. ii. Pop the top element from the stack `tracker`.
9. After processing the entire sequence, the string `result` will contain the minimum number sequence.

## Code Solution

``````import java.util.Stack;
/*
Java program for
Find minimum number from a ID sequence
*/
public class Decode
{
public void minimumNumber(String sequence)
{
// Get the length of sequence
int n = sequence.length();
String result = "";
if (n > 0)
{
// Create an empty tracker
Stack < Integer > tracker = new Stack < Integer > ();
// Execute this loop through by length of sequence
for (int i = 0; i <= n; ++i)
{
tracker.push(i + 1);
if (i == n || sequence.charAt(i) == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!tracker.empty())
{
result = result + tracker.peek();
// Remove top of tracker
tracker.pop();
}
}
}
}
// Display given sequence
System.out.println(" Given sequence : " + sequence);
// Display calculated result
System.out.println(" Result : " + result);
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
C++ program for
Find minimum number from a ID sequence
*/
class Decode
{
public: void minimumNumber(string sequence)
{
// Get the length of sequence
int n = sequence.length();
string result = "";
if (n > 0)
{
// Create and empty tracker
stack < int > tracker;
// Execute this loop through by length of sequence
for (int i = 0; i <= n; ++i)
{
tracker.push(i + 1);
if (i == n || sequence[i] == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!tracker.empty())
{
result = result  +  to_string(tracker.top());
// Remove top of tracker
tracker.pop();
}
}
}
}
// Display given sequence
cout << " Given sequence : " << sequence << endl;
// Display calculated result
cout << " Result : " << result << endl;
}
};
int main()
{
// Test
return 0;
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Find minimum number from a ID sequence
*/
public class Decode
{
public void minimumNumber(String sequence)
{
// Get the length of sequence
int n = sequence.Length;
String result = "";
if (n > 0)
{
// Create and empty tracker
Stack < int > tracker = new Stack < int > ();
// Execute this loop through by length of sequence
for (int i = 0; i <= n; ++i)
{
tracker.Push(i + 1);
if (i == n || sequence[i] == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!(tracker.Count == 0))
{
result = result + tracker.Peek();
// Remove top of tracker
tracker.Pop();
}
}
}
}
// Display given sequence
Console.WriteLine(" Given sequence : " + sequence);
// Display calculated result
Console.WriteLine(" Result : " + result);
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````package main

import "fmt"
import "strconv"
/*
Go program for
Find minimum number from a ID sequence
*/

func minimumNumber(sequence string) {
// Get the length of sequence
var n int = len(sequence)
var result string = ""
if n > 0 {
// Create and empty tracker
var tracker = make([]int,0)
// Execute this loop through by length of sequence
for i := 0 ; i <= n ; i++ {
tracker = append(tracker, i + 1)
if i == n || sequence[i] == 'I' {
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
for (len(tracker) != 0) {
result = result + strconv.Itoa(tracker[len(tracker) - 1])
// Remove top of tracker
tracker = tracker[: len(tracker) - 1]
}
}
}
}
// Display given sequence
fmt.Println(" Given sequence : ", sequence)
// Display calculated result
fmt.Println(" Result : ", result)
}
func main() {

// Test
minimumNumber("DDIIIDI")
minimumNumber("IDD")
minimumNumber("IIDDI")
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````<?php
/*
Php program for
Find minimum number from a ID sequence
*/
class Decode
{
public	function minimumNumber(\$sequence)
{
// Get the length of sequence
\$n = strlen(\$sequence);
\$result = "";
if (\$n > 0)
{
// Create and empty tracker
\$tracker = array();
// Execute this loop through by length of sequence
for (\$i = 0; \$i <= \$n; ++\$i)
{
array_push(\$tracker, \$i + 1);
if (\$i == \$n || \$sequence[\$i] == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!empty(\$tracker))
{
\$result = \$result.strval(end(\$tracker));
// Remove top of tracker
array_pop(\$tracker);
}
}
}
}
// Display given sequence
echo(" Given sequence : ".\$sequence."\n");
// Display calculated result
echo(" Result : ".\$result."\n");
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````/*
Node JS program for
Find minimum number from a ID sequence
*/
class Decode
{
minimumNumber(sequence)
{
// Get the length of sequence
var n = sequence.length;
var result = "";
if (n > 0)
{
// Create and empty tracker
var tracker = [];
// Execute this loop through by length of sequence
for (var i = 0; i <= n; ++i)
{
tracker.push(i + 1);
if (i == n || sequence.charAt(i) == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!(tracker.length == 0))
{
result = result + tracker[tracker.length - 1];
// Remove top of tracker
tracker.pop();
}
}
}
}
// Display given sequence
console.log(" Given sequence : " + sequence);
// Display calculated result
console.log(" Result : " + result);
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````#   Python 3 program for
#   Find minimum number from a ID sequence
class Decode :
def minimumNumber(self, sequence) :
#  Get the length of sequence
n = len(sequence)
result = ""
if (n > 0) :
#  Create and empty tracker
tracker = []
i = 0
#  Execute this loop through by length of sequence
while (i <= n) :
tracker.append(i + 1)
if (i == n or sequence[i] == 'I') :
#  When i equal to n or
#  When sequence at  i location is 'I'
#  Then Append the tracker element into result
while (not(len(tracker) == 0)) :
result = result + str(tracker[-1])
#  Remove top of tracker
tracker.pop()

i += 1

#  Display given sequence
print(" Given sequence : ", sequence)
#  Display calculated result
print(" Result : ", result)

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Given sequence :  DDIIIDI
Result :  32145768
Given sequence :  IDD
Result :  1432
Given sequence :  IIDDI
Result :  125436``````
``````#   Ruby program for
#   Find minimum number from a ID sequence
class Decode
def minimumNumber(sequence)
#  Get the length of sequence
n = sequence.length
result = ""
if (n > 0)
#  Create and empty tracker
tracker = []
i = 0
#  Execute this loop through by length of sequence
while (i <= n)
tracker.push(i + 1)
if (i == n || sequence[i] == 'I')
#  When i equal to n or
#  When sequence at  i location is 'I'
#  Then Append the tracker element into result
while ((tracker.length != 0))
result = result + tracker.last.to_s
#  Remove top of tracker
tracker.pop()
end

end

i += 1
end

end

#  Display given sequence
print(" Given sequence : ", sequence, "\n")
#  Display calculated result
print(" Result : ", result, "\n")
end

end

def main()
#  Test
end

main()``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436
``````
``````import scala.collection.mutable._;
/*
Scala program for
Find minimum number from a ID sequence
*/
class Decode()
{
def minimumNumber(sequence: String): Unit = {
// Get the length of sequence
var n: Int = sequence.length();
var result: String = "";
if (n > 0)
{
// Create and empty tracker
var tracker: Stack[Int] = new Stack[Int]();
var i: Int = 0;
// Execute this loop through by length of sequence
while (i <= n)
{
tracker.push(i + 1);
if (i == n || sequence.charAt(i) == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!tracker.isEmpty)
{
result = result + tracker.top.toString();
// Remove top of tracker
tracker.pop;
}
}
i += 1;
}
}
// Display given sequence
println(" Given sequence : " + sequence);
// Display calculated result
println(" Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Decode = new Decode();
// Test
}
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````
``````import Foundation;
/*
Swift 4 program for
Find minimum number from a ID sequence
*/
struct Stack
{
private
var items: [Int] = []
func peek()->Int
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Int)
{
items.insert(data, at: 0)
}
}
class Decode
{
func minimumNumber(_ seq: String)
{
let sequence = Array(seq);
// Get the length of sequence
let n: Int = sequence.count;
var result: String = "";
if (n > 0)
{
// Create and empty tracker
var tracker = Stack();
var i: Int = 0;
// Execute this loop through by length of sequence
while (i <= n)
{
tracker.push(i + 1);
if (i == n || sequence[i] == "I")
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!tracker.isEmpty())
{
result = result + String(tracker.peek());
// Remove top of tracker
tracker.pop();
}
}
i += 1;
}
}
// Display given sequence
print(" Given sequence : ", seq);
// Display calculated result
print(" Result : ", result);
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Given sequence :  DDIIIDI
Result :  32145768
Given sequence :  IDD
Result :  1432
Given sequence :  IIDDI
Result :  125436``````
``````import java.util.Stack;
/*
Kotlin program for
Find minimum number from a ID sequence
*/
class Decode
{
fun minimumNumber(sequence: String): Unit
{
// Get the length of sequence
val n: Int = sequence.length;
var result: String = "";
if (n > 0)
{
// Create and empty tracker
var tracker: Stack < Int > = Stack < Int > ();
var i: Int = 0;
// Execute this loop through by length of sequence
while (i <= n)
{
tracker.push(i + 1);
if (i == n || sequence.get(i) == 'I')
{
// When i equal to n or
// When sequence at  i location is 'I'
// Then Append the tracker element into result
while (!tracker.empty())
{
result = result + tracker.peek().toString();
// Remove top of tracker
tracker.pop();
}
}
i += 1;
}
}
// Display given sequence
println(" Given sequence : " + sequence);
// Display calculated result
println(" Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Given sequence : DDIIIDI
Result : 32145768
Given sequence : IDD
Result : 1432
Given sequence : IIDDI
Result : 125436``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the ID sequence. This is because we perform a single pass through the sequence, and for each character, we perform constant time operations of pushing and popping elements from the stack. The use of the stack does not significantly affect the overall time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.