Best Problems on Recursion | Recursion in C++

                        Recursion - I  

Print String in Reverse Objective: To print the string in reverse.  

Base Case: If the string is empty: 

                     return;  

Reverse print the remaining string using recursion, and print then print the current character. 

Time Complexity: O(N2) [ IMP] 

Space Complexity: O(N2) [ IMP] 

Time complexity will be O(N2) because s.substr(i) takes O(N) times and it is called O(N) times. 

Space complexity will be O(N2) because s.substr(i) gives a string of O(N) size and it is called O(N) times. 

FollowUp: Try to do this in O(N) time and space. Hint: Pass by reference and

indices. 


Move all ‘x’ to the end of the string If the string is empty: 

return “ “;  

If the current character ch is ‘x’, we add the resultant string  + ch,  

Else we return ch + resultant string 

Time Complexity: O(N2) [ IMP] 

Space Complexity: O(N2 ) [ IMP] 

Time complexity will be O(N2) because s.substr(i) takes O(N) times and it is called O(N) times. 

Space complexity will be O(N2) because s.substr(i) gives a string of O(N) size and it is called O(N) times. 

FollowUp: Try to do this in O(N) time and space. Hint: Pass by reference and indices. 

   

Remove Duplicates 

If the string is empty: //no duplicates return “”;  

If the current character ch is ‘x’, we return resultant string  + ch,  

Else we return ch + resultant string 

Time Complexity: O(N2) 

Space Complexity: O(N2) 

Time complexity will be O(N2) because s.substr(i) takes O(N) times and it is called O(N) times. 

Space complexity will be O(N2) because s.substr(i) gives a string of O(N) size and it is called O(N) times. 


Replace Pi If the string is empty:  

return “”;  If s[0] == ‘p’ and s[1] == ‘i’ :  

print(“3.14”) 

else: 

print(s[0]) 

Time Complexity: O(N2) 

Space Complexity: O(N2) 

FollowUp: Try to do this in O(N) time and space. Hint: Pass by reference and indices. 

  

                 

Print all the subsequences 

Objective: For each character, we have two choices, either we include it or not.  

Time Complexity: O(2n ) 

Space Complexity: O(2n ) 


Tower of Hanoi 

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 

1) Only one disk can be moved at a time. 

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 

3) No disk may be placed on top of a smaller disk. 

 

Idea: move all the n-1 tiles to helper, and then place the remaining tile to dest and then place those n-1 tiles back from helper to dest. 

Time Complexity: O(2n ) 

Space Complexity: O(1) 


Code for follow-ups: 

1. Reverse 

2. Replace PI 


Comments

Post a Comment

Popular posts from this blog

Arrays - Q's asked by Top MNC's

Image
            Arrays Challenge        Subarray with given sum    (Google, Amazon, Facebook) Problem Given an unsorted array A​o​ f size N​  ​of non-negative integers, find a continuous subarray which adds to a given number S​. Constraints 1 <= N <= 105​ 0 <= Ai <= 101​ 0 Example Input:​ N = 5, S = 12 A[] = {1,2,3,7,5} Output:​2​ 4 Explanation:​T​ he sum of elements from 2nd position to 4th position is 12. Solution Brute Force Solution ● Find sum of all possible subarrays. If any of the sum equates to S​ , o​ utput the starting and ending index of the subarray. Time Complexity : O​ (n2​ ​) Optimized Approach Steps: 1.    Keep the pointers st and en, and a variable currSum that stores the sum from st to en. 2.    alize st = 0, en = 0initi 3.    Increment en till currSum + a[en + 1] > S  4.    When 3rd condition occurs, start increasing st until currSum <= S. 5....
Read more

Subarrays - Challenges | Questions asked by Top MNC's |

Image
 Array Challenges  Maximum Sum Subarray Array   1. Brute Force:   Idea: For each subarray arr[i..j], calculate its sum.  Time Complexity: O(N3 )  Space Complexity: O(1)    2. Prefix Sum Technique:  Idea: For each subarray arr[i..j], calculate its sum. Using prefix sum can  reduce time to calculate the sum of arr[i..j] to O(1)  Time Complexity: O(N2 )  Space Complexity: O(N)     3. Kadane’s Algorithm:  Idea: Start taking the sum of the array, as soon as it gets negative, discard the current subarray, and start a new sum.  Time Complexity: O(N)  Space Complexity: O(1)      Maximum Sum Circular Subarray:    Idea: There will 2 cases,     To get the Min subarray we multiply the array by -1 and get the maximum sum subarray.  Time Complexity: O(N)     Pair Target Sum Problem  Find whether there exist 2 numbers that sum t...
Read more

Strings Challenges | C++ Placement

Image
 String Challenges  Challenge 1  UpperCase-LowerCase interconversion  Given a string s with both uppercase and lowercase latin characters (‘a’ - ‘z’).  Your task is convert whole string into   1. Lower Case  2. Upper Case    Base idea: ‘a’ - ‘A’ = 32  1. Lowercase to UpperCase Approach  1. Iterate over the string s and if s[i] is a lower case character, then update s[i] -= 32    2. UpperCase to LowerCase Approach  1. Iterate over the string s and if s[i] is a upper case character, then update s[i] +=32    Code:    Challenge 2 Form the biggest number  of integers, our task is to form the biggest number out of those numbers in the string.    Approach:  Sort the string in descending order using inbuilt sort function.    Code     Challenge 3 Max Frequency  s of latin characters, your task is to output the character which has  maximum f...
Read more