Form minimum number from given sequence

The problem “Form minimum number from given sequence” states that you are given some pattern of I’s and D’s only. The meaning of I stands for increasing and for decreasing we are provided with D. The problem statement asks to print the minimum number which satisfies the given pattern. We have to use the digits from 1-9 and no digits should be repeated.

Table of Contents

Example

DIID

Explanation

The first digit is 2 then after decreasing it next digit will be 1. Then increasing 2 will make 3 as the minimum digit which is greater than 2. And then we have to increase it again but since after again increasing, we have to decrease it. Since digits can’t be repeated. So we will increase it by 2 and then decrease it by 1.

So the output will become 2 1 3 5 4

Again we increase the current digit. But doing that will give us 4 and after decreasing that we will have to use either 1, 2, or 3. And all of these digits were already used. So we need to increase the current digit to 5. And that’s how we reach to the answer.

Algorithm to form minimum number from given sequence

Check if the given sequence length is greater than or equal to 9, if true then return -1.
Declare a char array of size n+1 and set the value of count to 1.
Start traversing the array from 0 to n(inclusively).
1. Check if i is equal to the n or the string’s current character is equal to “I”, if true then
  1. Traverse the array from the previous value of to -1.
    1. Update the values of the output array by doing the following steps.
      1. Increase the value of count and store it to the output array.
      2. Check if j is current index is greater than 0, and also the current character of the string is “I”, then, break.
Return result.

Explanation

Given a string and of I’s and D’s only, we are asked to print the pattern which can be formed with the given string. Here I refers to increasing that is we have to make or form a minimum number which can justify the given sequence. Suppose if we say DI, where D stands for decreasing minimum number such that 2 is followed by forming 21 as a minimum number. the digits can not be repeated, the number can only contain the digits from 1-9. After that, “I” is there, we should form a minimum increasing number. Since 21 is already there. We aim to form an increasing number. Thus 1 is followed by 3, because 2 is already in use, and after that 3 is the only number which can be joined.

With all of these concepts and ideas, we are asked to print that minimum number which follows and satisfies the given conditions. We are going to use the output array in which we all store our output to that character array. We made some conditions for data validation and verification. If we find the length of the string greater than or equal to 9. Then we return -1 as result because we are strictly ordered to use 1-9 digit and no digits can be repeated.

Traverse the string we have received as an input. If the current index is equal to the length of the string or the current character is equal to the “I”. Then only we proceed further. After that start traversing from the value previous to the current value(i), till -1 is reached. Inside this loop we keep on increasing the value of count and storing into the output array at index j+1. Then check if the value of j is greater than or equal to 0 and also if the current character is “I”. If true, then break the loop and proceed further for more characters.

Code

C++ code to form minimum number from given sequence

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}

Java code to form minimum number from given sequence

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}

Complexity Analysis

Time Complexity

O(N) where “N” is the length of the query string. First check that we enter inside the nested loop, only if we have reached the end or if the current index is I. And the nested loop runs in a backward direction and we come out of the loop if come across I. So we can say that we enter the nested loop when we encounter an I and work on indices that have D stored at them. Since each index can either have I or D. We are traversing over each character only one. Thus the time complexity is linear.

Space Complexity

O(N), because we have created an output character array to store the result. The space complexity for the problem is also linear.