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:
-
Input: "DDIIIDI" Output: "32145768"
-
Input: "IDD" Output: "1432"
-
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:
- Push the current number (starting from 1) onto the tracker stack.
- 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.
- 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
- Create a class called
Decode
. - Define a function called
minimumNumber
that takes the input sequence as a parameter. - Get the length of the sequence
n
. - Initialize an empty string called
result
to store the final sequence. - If the sequence is not empty, create an empty stack called
tracker
. - Iterate through the sequence from index 0 to n - 1 using a loop.
- Push the number (i + 1) onto the stack
tracker
. - 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 stacktracker
to the stringresult
. ii. Pop the top element from the stacktracker
. - 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)
{
// Add unique number
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)
{
Decode task = new Decode();
// Test
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
}
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)
{
// Add unique number
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()
{
Decode *task = new Decode();
// Test
task->minimumNumber("DDIIIDI");
task->minimumNumber("IDD");
task->minimumNumber("IIDDI");
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)
{
// Add unique number
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)
{
Decode task = new Decode();
// Test
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
}
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++ {
// Add unique number
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)
{
// Add unique number
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()
{
$task = new Decode();
// Test
$task->minimumNumber("DDIIIDI");
$task->minimumNumber("IDD");
$task->minimumNumber("IIDDI");
}
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)
{
// Add unique number
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()
{
var task = new Decode();
// Test
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
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) :
# Add unique number
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() :
task = Decode()
# Test
task.minimumNumber("DDIIIDI")
task.minimumNumber("IDD")
task.minimumNumber("IIDDI")
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)
# Add unique number
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()
task = Decode.new()
# Test
task.minimumNumber("DDIIIDI")
task.minimumNumber("IDD")
task.minimumNumber("IIDDI")
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)
{
// Add unique number
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
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
}
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)
{
// Add unique number
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()
{
let task: Decode = Decode();
// Test
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
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)
{
// Add unique number
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
{
val task: Decode = Decode();
// Test
task.minimumNumber("DDIIIDI");
task.minimumNumber("IDD");
task.minimumNumber("IIDDI");
}
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.
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.
New Comment