COL100 Assignment 7 -Solved

Heaven (In Lab Component) 
Mr. Page has found the stairway to heaven. The number of steps to go to heaven is N. He is currently 
at the 0 th stair and wishes to reach the Nth stair. Mr. Page can take 1 or 2, or 3 steps in a single jump. 
Mr. Page is not a mathematician and needs your help determining the number of ways in which he can 
reach heaven. 
For example, if N = 9 then some of the possible jump combinations are: (3, 3, 3),(2, 2, 2, 3),(3, 3, 2, 1).... 
For example, (3, 3, 3) is a valid jump combination because 3 + 3 + 3 = 9 and each jump covers 1, 2, or 3 
steps only. Similarly, for (2, 2, 2, 1), we have 2 + 2 + 2 + 3 = 9, so it is a valid combination. The total 
number of valid combinations of jumps will be 149 for the input N = 9, and Mr. Page only needs this 
number (not the list of all jump combinations). 
Your solution should run in linear time - O(N). Here N, is the number of steps to reach 
heaven. You have to write a short description (2-3 lines) of why your code has linear time 
complexity, write it inside the comments in the skeleton code. 
We have provided a skeleton code which takes input; type cast the input into int; call the func
tion heaven() and print the return value of the function heaven(). You have to only implement the 
function heaven() and return the output as integer — you must not print anything in the 
function. 
Input: The first line (only input line) of input will contain the value of N (only integer (int type); 
follow the skeleton code.). 
Return Output : Only return the total number of combinations of jumps (only integer (int type)). 
Some points to note: 
1. Any algorithm of time complexity more than O(N) will receive 0. As the stairs go to heaven, they 
might have large values. 
2. Combinations like (1, 3) and (3, 1) are considered distinct and are counted as 2 while combination 
like (1, 1) and (1, 1) are same and considered as 1 . 
Example 1: 
INPUT: 
1 300 
OUTPUT: 
1 15350287614359738671843506567023635268924281173051801861566524609184461020990367 
Example 2: 
INPUT: 
1 4 
OUTPUT: 
1 7 
EXPLANATION: 
Possible Combinations are [(3,1),(1,3),(2,2),(2,1,1),(1,2,1),(1,1,2),(1,1,1)]. Total 7 
22 Sorting 
You have been given a string that can contain digits (base 10) or letters(’a’-’z’ or ’A’-’Z’) only. You 
have to arrange the characters of this string in such a way that all occurrences of digits (0-9) which 
occur the odd number of times are moved to the front of the string in ascending order. The rest of the 
characters in the string are to be preserved. 
We have provided a skeleton code which takes input; call the function sortings () and print 
the returned output (which you have returned from function sortings ()). You have to only im
plement the function sortings() and return your output without printing anything in the 
function. 
Input: The first line of input (only input line) will contain string (can only contain digits (base 
10) or letters, follow skeleton code.). 
Return Output : Only "return" the string arranged in the manner mentioned above. (only string 
type and string contains only digits (base 10) or letters). 
Some points to note: 
1. In this question, we will be checking ONLY your output, so make sure to return correct format. 
Any output format mismatch will result in 0. 
2. Characters of strings can be case sensitive like "A" and "a" are different. 
Constraint: Length of string can be 0 ("") and can go as large as you can think. 
Example 1: 
INPUT: 
1 81454aDc5445bd 
OUTPUT: 
1 1555844aDc44bd 
EXPLANATION: 
Digits occurring the odd number of times are = 8, 1, 5. 
Also, 5 occurs three times. 
Remaining characters in the string are 44aDc44bd. 
So string returned by sortings() is 1555844aDc44bd 
Example 2: 
INPUT: 
1 322fcd223 
OUTPUT: 
1 322fcd223 
EXPLANATION: 
Here, digits occurring odd number of times are none. So the character left is the same as the original. 
33 Sorting a list
You have been given a list of strings and each string can contain digits (base 10) or letters only. For 
each string, you have to arrange the character of them (each string) in the same manner as mentioned 
as in Question 2. After this, for the resulting list of strings, you have to sort the list as follows - 
for each string, you have to extract all digits starting from index 0 until any non-digit character 
("a"-"z" or "A"-"Z") comes or the end of a string is encountered. Compare the extracted numer
ical value of one string with extracted numerical values of other strings to sort the list in ascending order. 
For example, if a string output of question 2 is "1112355744hkj887"; then extracted numerical 
value will be 1112355744. 
We have provided a skeleton code which takes input from you; call the function "sortings" and print 
the returned output (which you have returned from function "sortings"). You have to write your code, 
in function "sortings" only and "return" your output and do not need to print anything in 
function. 
Input: The first line of input will contain the number of strings in the list (int type). From the second 
line onwards, each line will contain a string of the list. ( str type, follow skeleton code.). 
Return Output : Only "return" the list of strings in the sorted manner as explained in the 
question. (Only return list , follow skeleton code). 
Some important points to note: 
1. In this question, we will be checking ONLY your Output, so make sure to return the correct 
format. Any output format mismatch will result in 0. 
2. Follow skeleton code, otherwise you can loose marks. You can make your own function which can 
be called from function "sortings" 
3. If for two strings, numerical values are the same, then either string can be in front of the other 
(order does not matter for these two). 
4. If no numerical value can be extracted from the string, then it is to be put at the last of list 
because it’s equivalent numerical value will be None and not 0. 
5. If length of string is 0 (""), then it’s equivalent numerical value will be None and not 0. 
Constraint: Length of string can be 0 ("") and can go as large as you can think. Length of list can 
be 0 that is ([]) and can go as large as you can think. Use of None is allowed. 
Example 1: 
INPUT: 
1 4 
2 44332211 
3 4412355bac889966 
4 abcdef5588447755 
5 44332211abc 
OUTPUT: 
1 ['1234455bac889966', '44332211', '44332211abc', 'abcdef5588447755'] 
EXPLANATION: 
41. The given list is [’44332211’, ’4412355bac889966’, ’abcdef5588447755’, ’44332211abc’]. 
2. After calling Question 2 for each string we get [’44332211’, ’1234455bac889966’, ’abcdef5588447755’, 
’44332211abc’]. 
3. Extracted numerical value are [44332211, 1234455, None, 44332211]. 
4. Sorting these numerical value we get [1234455, 44332211, 44332211, None]. 
5. Thus, Output list will be [’1234455bac889966’, ’44332211’, ’44332211abc’, ’abcdef5588447755’] 
Example 2: 
INPUT: 
1 3 
2 12334abc566 
3 7891010efg 
4 00000hgf0 
OUTPUT: 
1 ['00000hgf0', '124533abc66', '7891010efg'] 
5