Tutorialspoint.dev

Form minimum number from given sequence

Given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Devise an algorithm to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat.

Examples: 

   Input: D        Output: 21
   Input: I        Output: 12
   Input: DD       Output: 321
   Input: II       Output: 123
   Input: DIDI     Output: 21435
   Input: IIDDD    Output: 126543
   Input: DDIDDIID Output: 321654798

Source: Amazon Interview Question

We strongly recommend that you click here and practice it, before moving on to the solution.



Below are some important observations

Since digits can’t repeat, there can be at most 9 digits in output.

Also number of digits in output is one more than number of characters in input. Note that the first character of input corresponds to two digits in output.

Idea is to iterate over input array and keep track of last printed digit and maximum digit printed so far. Below is the implementation of above idea.

C++

// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include <iostream>
using namespace std;
  
// Prints the minimum number that can be formed from
// input sequence of I's and D's
void PrintMinNumberForPattern(string arr)
{
    // Initialize current_max (to make sure that
    // we don't use repeated character
    int curr_max = 0;
  
    // Initialize last_entry (Keeps track for
    // last printed digit)
    int last_entry = 0;
  
    int j;
  
    // Iterate over input array
    for (int i=0; i<arr.length(); i++)
    {
        // Initialize 'noOfNextD' to get count of
        // next D's available
        int noOfNextD = 0;
  
        switch(arr[i])
        {
        case 'I':
            // If letter is 'I'
  
            // Calculate number of next consecutive D's
            // available
            j = i+1;
            while (arr[j] == 'D' && j < arr.length())
            {
                noOfNextD++;
                j++;
            }
                
            if (i==0)
            {
                curr_max = noOfNextD + 2;
  
                // If 'I' is first letter, print incremented
                // sequence from 1
                cout << " " << ++last_entry;
                cout << " " << curr_max;
  
                // Set max digit reached
                last_entry = curr_max;
            }
            else
            {
                // If not first letter
  
                // Get next digit to print
                curr_max = curr_max + noOfNextD + 1;
  
                // Print digit for I
                last_entry = curr_max;
                cout << " " << last_entry;
            }
  
            // For all next consecutive 'D' print 
            // decremented sequence
            for (int k=0; k<noOfNextD; k++)
            {
                cout << " " << --last_entry;
                i++;
            }
            break;
  
        // If letter is 'D'
        case 'D':
            if (i == 0)
            {
                // If 'D' is first letter in sequence
                // Find number of Next D's available
                j = i+1;
                while (arr[j] == 'D' && j < arr.length())
                {
                    noOfNextD++;
                    j++;
                }
  
                // Calculate first digit to print based on 
                // number of consecutive D's
                curr_max = noOfNextD + 2;
  
                // Print twice for the first time
                cout << " " << curr_max << " " << curr_max - 1;
  
                // Store last entry
                last_entry = curr_max - 1;
            }
            else
            {
                // If current 'D' is not first letter
  
                // Decrement last_entry
                cout << " " << last_entry - 1;
                last_entry--;
            }
            break;
        }
    }
    cout << endl;
}
  
// Driver program to test above
int main()
{
    PrintMinNumberForPattern("IDID");
    PrintMinNumberForPattern("I");
    PrintMinNumberForPattern("DD");
    PrintMinNumberForPattern("II");
    PrintMinNumberForPattern("DIDI");
    PrintMinNumberForPattern("IIDDD");
    PrintMinNumberForPattern("DDIDDIID");
    return 0;
}

PHP

<?php
// PHP program to print minimum
// number that can be formed
// from a given sequence of 
// Is and Ds
  
// Prints the minimum number 
// that can be formed from
// input sequence of I's and D's
function PrintMinNumberForPattern($arr)
{
    // Initialize current_max 
    // (to make sure that
    // we don't use repeated 
    // character
    $curr_max = 0;
  
    // Initialize last_entry 
    // (Keeps track for
    // last printed digit)
    $last_entry = 0;
  
    $j;
  
    // Iterate over
    // input array
    for ($i = 0; $i < strlen($arr); $i++)
    {
        // Initialize 'noOfNextD'
        // to get count of
        // next D's available
        $noOfNextD = 0;
  
        switch($arr[$i])
        {
        case 'I':
            // If letter is 'I'
  
            // Calculate number of 
            // next consecutive D's
            // available
            $j = $i + 1;
            while ($arr[$j] == 'D' && 
                   $j < strlen($arr))
            {
                $noOfNextD++;
                $j++;
            }
              
            if ($i == 0)
            {
                $curr_max = $noOfNextD + 2;
  
                // If 'I' is first letter, 
                // print incremented
                // sequence from 1
                echo " " , ++$last_entry;
                echo " " , $curr_max;
  
                // Set max 
                // digit reached
                $last_entry = $curr_max;
            }
            else
            {
                // If not first letter
  
                // Get next digit
                // to print
                $curr_max = $curr_max + 
                            $noOfNextD + 1;
  
                // Print digit for I
                $last_entry = $curr_max;
                echo " " , $last_entry;
            }
  
            // For all next consecutive 'D' 
            // print decremented sequence
            for ($k = 0; $k < $noOfNextD; $k++)
            {
                echo " " , --$last_entry;
                $i++;
            }
            break;
  
        // If letter is 'D'
        case 'D':
            if ($i == 0)
            {
                // If 'D' is first letter 
                // in sequence. Find number
                // of Next D's available
                $j = $i+1;
                while (($arr[$j] == 'D') && 
                       ($j < strlen($arr)))
                {
                    $noOfNextD++;
                    $j++;
                }
  
                // Calculate first digit 
                // to print based on 
                // number of consecutive D's
                $curr_max = $noOfNextD + 2;
  
                // Print twice for
                // the first time
                echo " " , $curr_max , 
                     " " ,$curr_max - 1;
  
                // Store last entry
                $last_entry = $curr_max - 1;
            }
            else
            {
                // If current 'D' 
                // is not first letter
  
                // Decrement last_entry
                echo " " , $last_entry - 1;
                $last_entry--;
            }
            break;
        }
    }
      
echo " ";
}
  
// Driver Code
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
  
// This code is contributed by aj_36
?>


Output:

 1 3 2 5 4
 1 2
 3 2 1
 1 2 3
 2 1 4 3 5
 1 2 6 5 4 3
 3 2 1 6 5 4 7 9 8

This solution is suggested by Swapnil Trambake.

Alternate Solution:
Let’s observe a few facts in case of minimum number:

  • The digits can’t repeat hence there can be 9 digits at most in output.
  • To form a minimum number , at every index of the output, we are interested in the minimum number which can be placed at that index.

The idea is to iterate over the entire input array , keeping track of the minimum number (1-9) which can be placed at that position of the output.

The tricky part of course occurs when ‘D’ is encountered at index other than 0. In such a case we have to track the nearest ‘I’ to the left of ‘D’ and increment each number in the output vector by 1 in between ‘I’ and ‘D’.

We cover the base case as follows:



  • If the first character of input is ‘I’ then we append 1 and 2 in the output vector and the minimum available number is set to 3 .The index of most recent ‘I’ is set to 1.
  • If the first character of input is ‘D’ then we append 2 and 1 in the output vector and the minimum available number is set to 3, and the index of most recent ‘I’ is set to 0.

Now we iterate the input string from index 1 till its end and:

  • If the character scanned is ‘I’ ,minimum value which has not been used yet is appended to the output vector .We increment the value of minimum no. available and index of most recent ‘I’ is also updated.
  • If the character scanned is ‘D’ at index i of input array, we append the ith element from output vector in the output and track the nearest ‘I’ to the left of ‘D’ and increment each number in the output vector by 1 in between ‘I’ and ‘D’.

Following is the program for the same:

C++

// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include<bits/stdc++.h>
using namespace std;
  
void printLeast(string arr)
{
    // min_avail represents the minimum number which is
    // still available for inserting in the output vector.
    // pos_of_I keeps track of the most recent index
    // where 'I' was encountered w.r.t the output vector
    int min_avail = 1, pos_of_I = 0;
  
    //vector to store the output
    vector<int>v;
  
    // cover the base cases
    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;
    }
  
    // Traverse rest of the input
    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++;
        }
    }
  
    // print the number
    for (int i=0; i<v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
}
  
// Driver program to check the above function
int main()
{
    printLeast("IDID");
    printLeast("I");
    printLeast("DD");
    printLeast("II");
    printLeast("DIDI");
    printLeast("IIDDD");
    printLeast("DDIDDIID");
    return 0;
}

Java

// Java program to print minimum number that can be formed 
// from a given sequence of Is and Ds 
import java.io.*;
import java.util.*;
public class GFG {
  
       static void printLeast(String arr)
       {
              // min_avail represents the minimum number which is 
              // still available for inserting in the output vector. 
              // pos_of_I keeps track of the most recent index 
              // where 'I' was encountered w.r.t the output vector 
              int min_avail = 1, pos_of_I = 0; 
  
              //vector to store the output
              ArrayList<Integer> al = new ArrayList<>();
                
              // cover the base cases
              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; 
              }
  
              // Traverse rest of the input
              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++;
                   }
              }
  
              // print the number
              for (int i = 0; i < al.size(); i++)
                   System.out.print(al.get(i) + " ");
              System.out.println();
       }
  
  
       // Driver code
       public static void main(String args[])
       {
              printLeast("IDID"); 
              printLeast("I"); 
              printLeast("DD"); 
              printLeast("II"); 
              printLeast("DIDI"); 
              printLeast("IIDDD"); 
              printLeast("DDIDDIID"); 
       }
}
// This code is contributed by rachana soma


Output:

1 3 2 5 4 
1 2 
3 2 1 
1 2 3 
2 1 4 3 5 
1 2 6 5 4 3 
3 2 1 6 5 4 7 9 8

This solution is suggested by Ashutosh Kumar.

 

Method 3
We can that when we encounter I, we got numbers in increasing order but if we encounter ‘D’, we want to have numbers in decreasing order. Length of the output string is always one more than the input string. So loop is from 0 till the length of the sting. We have to take numbers from 1-9 so we always push (i+1) to our stack. Then we check what is the resulting character at the specified index.So,there will be two cases which are as follows:-
Case 1: If we have encountered I or we are at the last character of input string,then pop from the stack and add it to the end of the output string until the stack gets empty.
Case 2: If we have encountered D, then we want the numbers in decreasing order.so we just push (i+1) to our stack.

C++

// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include <bits/stdc++.h>
using namespace std;
  
// Function to decode the given sequence to construct
// minimum number without repeated digits
void PrintMinNumberForPattern(string seq)
{
    // result store output string
    string result;
  
    // create an empty stack of integers
    stack<int> stk;
  
    // run n+1 times where n is length of input sequence
    for (int i = 0; i <= seq.length(); i++)
    {
        // push number i+1 into the stack
        stk.push(i + 1);
  
        // if all characters of the input sequence are
        // processed or current character is 'I'
        // (increasing)
        if (i == seq.length() || seq[i] == 'I')
        {
            // run till stack is empty
            while (!stk.empty())
            {
                // remove top element from the stack and
                // add it to solution
                result += to_string(stk.top());
                result += " ";
                stk.pop();
            }
        }
    }
  
    cout << result << endl;
}
  
// main function
int main()
{
    PrintMinNumberForPattern("IDID");
    PrintMinNumberForPattern("I");
    PrintMinNumberForPattern("DD");
    PrintMinNumberForPattern("II");
    PrintMinNumberForPattern("DIDI");
    PrintMinNumberForPattern("IIDDD");
    PrintMinNumberForPattern("DDIDDIID");
    return 0;
}

Java

import java.util.Stack;
  
// Java program to print minimum number that can be formed
// from a given sequence of Is and Ds
class GFG {
  
// Function to decode the given sequence to construct
// minimum number without repeated digits
    static void PrintMinNumberForPattern(String seq) {
        // result store output string
        String result = "";
  
        // create an empty stack of integers
        Stack<Integer> stk = new Stack<Integer>();
  
        // run n+1 times where n is length of input sequence
        for (int i = 0; i <= seq.length(); i++) {
            // push number i+1 into the stack
            stk.push(i + 1);
  
            // if all characters of the input sequence are
            // processed or current character is 'I'
            // (increasing)
            if (i == seq.length() || seq.charAt(i) == 'I') {
                // run till stack is empty
                while (!stk.empty()) {
                    // remove top element from the stack and
                    // add it to solution
                    result += String.valueOf(stk.peek());
                    result += " ";
                    stk.pop();
                }
            }
        }
  
        System.out.println(result);
    }
  
// main function
    public static void main(String[] args) {
        PrintMinNumberForPattern("IDID");
        PrintMinNumberForPattern("I");
        PrintMinNumberForPattern("DD");
        PrintMinNumberForPattern("II");
        PrintMinNumberForPattern("DIDI");
        PrintMinNumberForPattern("IIDDD");
        PrintMinNumberForPattern("DDIDDIID");
    }
}
// This code is contributed by PrinciRaj1992 

C#

// C# program to print minimum number that can be formed
// from a given sequence of Is and Ds
using System;
using System.Collections;
public class GFG {
   
// Function to decode the given sequence to construct
// minimum number without repeated digits
    static void PrintMinNumberForPattern(String seq) {
        // result store output string
        String result = "";
   
        // create an empty stack of integers
        Stack stk = new Stack();
   
        // run n+1 times where n is length of input sequence
        for (int i = 0; i <= seq.Length; i++) {
            // push number i+1 into the stack
            stk.Push(i + 1);
   
            // if all characters of the input sequence are
            // processed or current character is 'I'
            // (increasing)
            if (i == seq.Length || seq[i] == 'I') {
                // run till stack is empty
                while (stk.Count!=0) {
                    // remove top element from the stack and
                    // add it to solution
                    result += String.Join("",stk.Peek());
                    result += " ";
                    stk.Pop();
                }
            }
        }
   
        Console.WriteLine(result);
    }
   
// main function
    public static void Main() {
        PrintMinNumberForPattern("IDID");
        PrintMinNumberForPattern("I");
        PrintMinNumberForPattern("DD");
        PrintMinNumberForPattern("II");
        PrintMinNumberForPattern("DIDI");
        PrintMinNumberForPattern("IIDDD");
        PrintMinNumberForPattern("DDIDDIID");
    }
}
// This code is contributed by 29AjayKumar


Output: 

1 3 2 5 4 
1 2 
3 2 1 
1 2 3 
2 1 4 3 5 
1 2 6 5 4 3 
3 2 1 6 5 4 7 9 8

Time Complexity : O(n)
Auxiliary Space : O(n)

This method is contributed by Roshni Agarwal.

Method 4 (Using two pointers)
Observation



  1. Since we have to find minimum number without repeating digits, maximum length of output can be 9 (using each 1-9 digits once)
  2. Length of the output will be exactly one greater than input length.
  3. The idea is to iterate over the string and do the following if current character is ‘I’ or string is ended.
    1. Assign count in increasing order to each element from current-1 to the next left index of ‘I’ (or starting index is reached).
    2. Increase the count by 1.
Input  :  IDID
Output : 13254

Input  :  I
Output : 12

Input  :  DD
Output : 321

Input  :  II
Output : 123

Input  :  DIDI
Output : 21435

Input  :  IIDDD
Output : 126543

Input  :  DDIDDIID
Output : 321654798

Below is the implementation of above approach:

C++

// C++ program of above approach
#include <bits/stdc++.h> 
using namespace std; 
    
// Returns minimum number made from given sequence without repeating digits 
string getMinNumberForPattern(string seq) 
{ 
    int n = seq.length();
  
    if (n >= 9)
        return "-1";
  
    string result(n+1, ' '); 
  
    int count = 1;  
  
    // The loop runs for each input character as well as 
    // one additional time for assigning rank to remaining characters
    for (int i = 0; i <= n; i++) 
    { 
        if (i == n || seq[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                result[j + 1] = '0' + count++;
                if(j >= 0 && seq[j] == 'I')
                    break;
            }
        }
    }
    return result;
}
    
// main function 
int main() 
{
    string inputs[] = {"IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID"};
  
    for (string input : inputs)
    {
        cout << getMinNumberForPattern(input) << " ";
    }
    return 0; 
}

Java

// Java program of above approach
import java.io.IOException;
  
public class Test
{
    // Returns minimum number made from given sequence without repeating digits
    static String getMinNumberForPattern(String seq)
    {
        int n = seq.length();
  
        if (n >= 9)
            return "-1";
  
        char result[] = new char[n + 1];
  
        int count = 1;
  
        // The loop runs for each input character as well as 
        // one additional time for assigning rank to each remaining characters
        for (int i = 0; i <= n; i++)
        {
            if (i == n || seq.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    result[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && seq.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(result);
    }
      
    public static void main(String[] args) throws IOException
    {
        String inputs[] = { "IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID" };
  
        for(String input : inputs)
        {
            System.out.println(getMinNumberForPattern(input));
        }
    }
}

Python3

# Python3 program of above approach
      
# Returns minimum number made from 
# given sequence without repeating digits 
def getMinNumberForPattern(seq):
    n = len(seq) 
  
    if (n >= 9):
        return "-1"
  
    result = [None] * (n + 1) 
  
    count = 1
  
    # The loop runs for each input character 
    # as well as one additional time for 
    # assigning rank to remaining characters
    for i in range(n + 1):
        if (i == n or seq[i] == 'I'):
            for j in range(i - 1, -2, -1):
                result[j + 1] = int('0' + str(count))
                count += 1
                if(j >= 0 and seq[j] == 'I'): 
                    break
    return result
      
# Driver Code 
if __name__ == '__main__':
    inputs = ["IDID", "I", "DD", "II", 
              "DIDI", "IIDDD", "DDIDDIID"]
    for Input in inputs:
        print(*(getMinNumberForPattern(Input)))
  
# This code is contributed by PranchalK

C#

// C# program of above approach 
using System; 
class GFG
{ 
      
// Returns minimum number made from given
// sequence without repeating digits 
static String getMinNumberForPattern(String seq) 
{ 
    int n = seq.Length; 
  
    if (n >= 9) 
        return "-1"; 
  
    char []result = new char[n + 1]; 
  
    int count = 1; 
  
    // The loop runs for each input character
    // as well as one additional time for
    // assigning rank to each remaining characters 
    for (int i = 0; i <= n; i++) 
    { 
        if (i == n || seq[i] == 'I') 
        { 
            for (int j = i - 1; j >= -1; j--) 
            { 
                result[j + 1] = (char) ((int) '0' + count++); 
                if (j >= 0 && seq[j] == 'I') 
                    break; 
            } 
        } 
    } 
    return new String(result); 
} 
  
// Driver Code
public static void Main()
{ 
    String []inputs = { "IDID", "I", "DD", "II", 
                        "DIDI", "IIDDD", "DDIDDIID" }; 
  
    foreach(String input in inputs) 
    { 
        Console.WriteLine(getMinNumberForPattern(input)); 
    } 
} 
} 
  
// This code is contributed by Rajput-Ji


Output:

13254
12
321
123
21435
126543
321654798

Time Complexity : O(N)
Auxiliary Space : O(1)

This solution is suggested by Brij Desai.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

tags:

Arrays Stack Strings Amazon Goldman Sachs Amazon Goldman Sachs Arrays Strings Stack
Prev Next
More topics on Stack Data Structure

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Stack Data Structu... Stack | Set 4 (Evaluation of P...
Stack Data Structu... Check for balanced parentheses...
Stack Data Structu... Reversing the first K elements...
Stack Data Structu... Reversing a Queue
Stack Data Structu... The Stock Span Problem
Stack Data Structu... Postfix to Prefix Conversion