Table of Contents
Problem Statement
The problem “Form Minimum Number From Given Sequence states that you are given a string s of length/size n representing a pattern of characters ‘I’ i.e. increasing and ‘D’ i.e. decreasing only. Print the minimum number for the given pattern with unique digits from 1-9.
For instance –
Example
s = "DD"
3 2 1
Explanation: Since the digits can’t be negative, we will select 3 as the first digit and then keep on decrementing the upcoming digits.
s = "DIDI"
2 1 4 3 5
Method 1
Algorithm
- Initialize a string s.
- Traverse through the given string s and check if the current character in the string is equal to ‘I’, calculate the total number of next consecutive characters equal to ‘D’ in the given string.
- If the character ‘I’ is the first character in the string, print the increasing pattern starting from 1 else print the next digit.
- Print the decreasing pattern for all the next consecutive characters equal to ‘D’ in the given string.
- Similarly, check if the current character in the string is equal to ‘D’, check if the character ‘D’ is the first character in the string, count all the ‘D’s in the string and print the pattern accordingly.
- Else decrement the last entry by 1.
Complexity Analysis
Time Complexity
O(n) where n is the length of the given string s.
Space Complexity
O(n) because we used space to store the characters of the given string.
Code
C++ Program to form minimum number from given sequence
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
int curr_max = 0;
int last_entry = 0;
int j;
for(int i=0; i<arr.length(); i++){
int noOfNextD = 0;
switch(arr[i]){
case 'I':
j = i+1;
while (arr[j] == 'D' && j < arr.length()){
noOfNextD++;
j++;
}
if (i==0){
curr_max = noOfNextD + 2;
cout << " " << ++last_entry;
cout << " " << curr_max;
last_entry = curr_max;
}
else{
curr_max = curr_max + noOfNextD + 1;
last_entry = curr_max;
cout << " " << last_entry;
}
for (int k=0; k<noOfNextD; k++){
cout << " " << --last_entry;
i++;
}
break;
case 'D':
if (i == 0){
j = i+1;
while (arr[j] == 'D' && j < arr.length()){
noOfNextD++;
j++;
}
curr_max = noOfNextD + 2;
cout << " " << curr_max << " " << curr_max - 1;
last_entry = curr_max - 1;
}
else{
cout << " " << last_entry - 1;
last_entry--;
}
break;
}
}
cout << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}1 3 2 5 4
Java Program to form minimum number from given sequence
class MinNum{
static void FormMinNumber(String arr){
int curr_max = 0;
int last_entry = 0;
int j;
for (int i = 0; i < arr.length(); i++){
int noOfNextD = 0;
switch (arr.charAt(i)){
case 'I':
j = i + 1;
while (j < arr.length() && arr.charAt(j) == 'D'){
noOfNextD++;
j++;
}
if (i == 0){
curr_max = noOfNextD + 2;
System.out.print(" " + ++last_entry);
System.out.print(" " + curr_max);
last_entry = curr_max;
}
else{
curr_max = curr_max + noOfNextD + 1;
last_entry = curr_max;
System.out.print(" " + last_entry);
}
for (int k = 0; k < noOfNextD; k++){
System.out.print(" " + --last_entry);
i++;
}
break;
case 'D':
if (i == 0){
j = i + 1;
while (j < arr.length()&&arr.charAt(j) == 'D'){
noOfNextD++;
j++;
}
curr_max = noOfNextD + 2;
System.out.print(" " + curr_max + " " + (curr_max - 1));
last_entry = curr_max - 1;
}
else{
System.out.print(" " + (last_entry - 1));
last_entry--;
}
break;
}
}
System.out.println();
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}1 3 2 5 4
Method 2
Algorithm
- Initialize a string s.
- Create a vector v of type integer.
- Check if the first character of the given string is ‘I’, push 1 and 2 in the vector and set the minimum available number as 3 and position of ‘I’ as 1.
- Else push 2 and 1 in the vector and set the minimum available number as 3 and position of ‘I’ as 0.
- Traverse through the string starting from 1 and check if the current character of the given string is ‘I’, push the minimum available number in the vector, increment the minimum available number and update the position of ‘I’ as current index + 1.
- Else push the current element in vector in vector again and increment the minimum available number.
- Print the vector.
Complexity Analysis
Time Complexity
O(n) where n is the length of the given string s.
Space Complexity
O(n) because we used space to store the characters of the given string.
Code
C++ Program to form minimum number from given sequence
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
int min_avail = 1, pos_of_I = 0;
vector<int>v;
if (arr[0]=='I'){
v.push_back(1);
v.push_back(2);
min_avail = 3;
pos_of_I = 1;
}
else{
v.push_back(2);
v.push_back(1);
min_avail = 3;
pos_of_I = 0;
}
for (int i=1; i<arr.length(); i++){
if (arr[i]=='I'){
v.push_back(min_avail);
min_avail++;
pos_of_I = i+1;
}
else{
v.push_back(v[i]);
for (int j=pos_of_I; j<=i; j++){
v[j]++;
}
min_avail++;
}
}
for (int i=0; i<v.size(); i++){
cout << v[i] << " ";
}
cout << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}1 3 2 5 4
Java Program to form minimum number from given sequence
import java.util.*;
class MinNum{
static void FormMinNumber(String arr){
int min_avail = 1, pos_of_I = 0;
ArrayList<Integer> al = new ArrayList<>();
if (arr.charAt(0) == 'I'){
al.add(1);
al.add(2);
min_avail = 3;
pos_of_I = 1;
}
else{
al.add(2);
al.add(1);
min_avail = 3;
pos_of_I = 0;
}
for (int i = 1; i < arr.length(); i++){
if (arr.charAt(i) == 'I'){
al.add(min_avail);
min_avail++;
pos_of_I = i + 1;
}
else{
al.add(al.get(i));
for (int j = pos_of_I; j <= i; j++) {
al.set(j, al.get(j) + 1);
}
min_avail++;
}
}
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
System.out.println();
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}1 3 2 5 4
Method 3
Algorithm
- Initialize a string s.
- Create a stack data structure.
- Traverse through the string and push the current index + 1 in the stack at every iteration. Chcek if the current index is equal to the length of the string or the current character in the string is equal to ‘I’, while the stack is not empty concatenate all the elements of the stack in a string.
- Print the string.
Complexity Analysis
Time Complexity
O(n) where n is the length of the given string s.
Space Complexity
O(n) because we used space to store the characters of the given string.
Code
C++ Program to form minimum number from given sequence
#include <bits/stdc++.h>
using namespace std;
void FormMinNumber(string arr){
string result;
stack<int> stk;
for (int i = 0; i <= arr.length(); i++){
stk.push(i + 1);
if (i == arr.length() || arr[i] == 'I'){
while (!stk.empty()){
result += to_string(stk.top());
result += " ";
stk.pop();
}
}
}
cout << result << endl;
}
int main(){
string s = "IDID";
FormMinNumber(s);
return 0;
}1 3 2 5 4
Java Program to form minimum number from given sequence
import java.util.*;
class MinNum{
static void FormMinNumber(String arr){
String result = "";
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i <= arr.length(); i++) {
stk.push(i + 1);
if (i == arr.length() || arr.charAt(i) == 'I') {
while (!stk.empty()) {
result += String.valueOf(stk.peek());
result += " ";
stk.pop();
}
}
}
System.out.println(result);
}
public static void main(String[] args){
String s = "IDID";
FormMinNumber(s);
}
}1 3 2 5 4
Method 4
Algorithm
- Initialize a string s.
- Check if the length of the given string is greater than or equal to 9, print -1, and return.
- Traverse through the given string and check if the current index is equal to the length of the string or the current character in the string is equal to ‘I’, Traverse again from the current index – 1 to 0 and update the result of current index + 1.
- If the current index is greater than or equal to 0 and the current character in the string is equal to ‘I’, break the loop.
- Print result.
Complexity Analysis
Time Complexity
O(n) where n is the length of the given string s.
Space Complexity
O(n) because we used space to store the characters of the given string.
Code
C++ Program to form minimum number from given sequence
#include <bits/stdc++.h>
using namespace std;
string FormMinNumber(string arr){
int n = arr.length();
if(n >= 9){
return "-1";
}
string result(n+1, ' ');
int count = 1;
for (int i = 0; i <= n; i++){
if (i == n || arr[i] == 'I'){
for (int j = i - 1 ; j >= -1 ; j--){
result[j + 1] = '0' + count++;
if(j >= 0 && arr[j] == 'I'){
break;
}
}
}
}
return result;
}
int main(){
string s = "IDID";
cout<<FormMinNumber(s);
return 0;
}13254
Java Program to form minimum number from given sequence
import java.util.*;
class MinNum{
static String FormMinNumber(String arr){
int n = arr.length();
if (n >= 9){
return "-1";
}
char result[] = new char[n + 1];
int count = 1;
for (int i = 0; i <= n; i++){
if (i == n || arr.charAt(i) == 'I'){
for (int j = i - 1; j >= -1; j--){
result[j + 1] = (char) ((int) '0' + count++);
if (j >= 0 && arr.charAt(j) == 'I'){
break;
}
}
}
}
return new String(result);
}
public static void main(String[] args){
String s = "IDID";
System.out.println(FormMinNumber(s));
}
}13254