Form minimum number from given sequence of D's and I's

When given a pattern containing D's and I's, D for decreasing and I for increasing. This function will print minimum number from given sequence of D's and I's. Output should contain only digits from 1-9 and no digit should repeat in the number

Example 1

INPUT :
DIDI

OUTPUT :
21435

Example 2

INPUT :
DIDII

OUTPUT :
214356

In example 1, the given sequence is DIDI and the output number is 21435. For first letter "D" their is a decrement in number ie, 2 to 1. For second letter "I" their is an increment in number ie, from 1 to 4, similarly for other letters. One more possible answer for this sequence is 94856 , but we need the minimum number as the output. So, 94856 is the wrong answer.

From the given question we can conclude that, If the input sequence length is l then the output number length will be of length l+1 and maximum input sequence length can be of 8.

In this method, while traversing the array we will keep track of maximum digit and last printed digit that has encourted so far.

Algorithm

1. Till the end of the array

case 1 :

If the element is I

a. Calculate the number of consecutive D's that are present after the present element I and store it in noofDs variable.

b. If it is the first element, to print the first two elements in the output, make the maximum variable equal to number of consecutive D's present plus 2 ie, max = noofDs + 2. Here, maximum variable keeps track of maximum digit till now. Print 1 and print maximim.

c. If it is not the first element, then make the maximum equal to previous maximum plus noofDs plus 1 ie, max = max + noofDs + 1 and make the last_printed equal to the maximum and print last_printed. Here last_printed keeps track of last printed digit.

case 2 :

If the element is D

a. If D is the first element in the sequence, calculate the number of consecutive D's that are present after the present element D and store it in noofDs variable

b. Calculating the first digit to print based on no of D's. So, make the maximum variable equal to number of consecutive D's present plus 2 ie, max = noofDs + 2

c. First two digits in the output will be maximum and maximum -1 . Make the last_printed equal to maximum -1.

d. If it is not the first element, then decrement the last_printed and print the last_printed.

C++ Program

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

int minNumber(string arr)
{
	int maximum = 0;
	int last_printed = 0;
	for (int i = 0; i < arr.length(); ++i)
	{
		int noofDs = 0;  //Number of D's that are present after the element
		switch(arr[i])
		{
			case 'I':
			{
	            int j = i+1;
	            while (arr[j] == 'D' && j < arr.length())
	            {
	                noofDs++;  //counting number of consecutive D's
	                j++;
	            }
	               
	            if (i==0) //if it is the first element
	            {
	                maximum = noofDs + 2; 
	 
	                cout << " " << "1"; //print the first two elementss in the output
	                cout << " " << maximum;
	 
	                // Set max digit reached
	                last_printed = maximum;
	            }
	            else
	            {
	                // If not first letter 
	                maximum = maximum + noofDs + 1;
	 
	                // Print digit for I
	                last_printed = maximum;
	                cout << " " << last_printed;
	            }
	 
	            // For all next consecutive D's print the decrement sequence
	            for (int k=0; k<noofDs; k++)
	            {
	                cout << " " << --last_printed;
	                i++;
	            }
	            break;
	        }
        	case 'D':
        	{
	        	if (i == 0)
	            {
	                // If 'D' is first letter in sequence
	                int j = i+1;
	                while (arr[j] == 'D' && j < arr.length())
	                {
	                    noofDs++;
	                    j++;
	                }
	 
	                // Calculate first digit to print 
	                maximum = noofDs + 2;
	 
	                // Print the first two elements
	                cout << " " << maximum << " " << maximum - 1;
	 
	                // Store last entry
	                last_printed = maximum - 1;
	            }
	            else
	            {
	                // If current 'D' is not first letter
	 
	                // Decrement last_printed
	                cout << " " << last_printed - 1;
	                last_printed--;
	            }
	            break;
	            }    

		}

	}
	cout<<endl;
}
int main()
{
	minNumber("DIDI");
	return 0;
}
Try It


Next > < Prev
Scroll to Top