Skip to main content

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)
			{
				// 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.

Last updated on by Kalkicode




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.

New Comment