Introduction
The stated problem "Form minimum number from given sequence" had been asked in Amazon Entrance Examination. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach and the basic simple mathematics of the programmer.
We will discuss how to form a minimum number from a given sequence. Let's check the problem statement first to know more about the problem.
Also See, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
Given problem "Form minimum number from given sequence" states that we have a pattern containing only I's and D's in it, where I means increasing and D means decreasing. We have to write a schematic code for the above-mentioned problem. One rule is that you take digits from 1 to 9 and don't repeat any digits.
Sample Examples
Example 1
Input
DIDI
Output
21435
Explanation: The pattern of the elementary problem is DIDI, and the output number is 21435. There is a decrement in number for the first letter, "D," i.e., 2 to 1. There is an increment in number for the second letter, "I," i.e., from 1 to 4, similarly to other letters.
Example 2
Input
DDIDDIIDOutput
321654798
Explanation: The pattern of the elementary problem is DDIDDIID, and the output number is 321654798. There is a decrement in number for the first letter, "D," i.e., 3 to 2. There is an increment in number for the third letter, "I," i.e., from 1 to 6, similarly to other letters.
Brute Force Approach
In the Brute Force Approach, we assume the smallest number as the solution and continue shifting the digits until we reach a D. There's no need to go back to get the index. Follow the steps given below to understand the given problem more precisely:
-
For len(s)+1, start with the smallest number.
-
Iterate to the end of the digits list, keeping track of the first D in a sequence of Ds, starting with the second digit (index 1) and first character (D)
-
When we come across a D:
Change the current index digit to the first D in the sequence.
-
When we come across an I:
Reset the last known location of D. There's nothing to move because the digit is correctly placed.
-
When we come across a D:
Implementation
def sequence(s: str):
if not s or len(s) <= 0:
return ""
main_list = ["1"]
for i in range(1, len(s) + 1):
main_list.append(f'{i + 1}')
last_D = -1
for i in range(1, len(main_list)):
if s[i - 1] == 'D':
if last_D < 0:
last_D = i - 1
v =main_list[i]
del main_list[i]
main_list.insert(last_D, v)
else:
last_D = -1
return main_list
# Function call
print(sequence("IDID"))
print(sequence("I"))
print(sequence("IIDDD"))
print(sequence("DDIDDIID" ))
Output
Time Complexity
The time complexity of the stated problem “Form minimum number from given sequence” is O(N), because the loop will run N times in the stated problem. Here, N is the number of characters in the given sequence.
Space Complexity
The space complexity of the stated problem “Form minimum number from given sequence” is O(N), because it is taking N times space in the given solution. Here, N is the number of characters in the given sequence.
Check out this problem - Shortest Common Supersequence.
84+ registered 