Hello and welcome to a new part of competitive programming with Python where we are exploring Recursion problems in-depth and in this article, we will be solving a little bit more advanced problems efficiently. I hope that you are ready to begin without much explanation.
Table of Contents
1) Kth Symbol in Grammar
One of the most popular Leetcode problem statements and famous interview questions asked in different ways.
Problem Statement - We are given 2 Numbers N and K. Task is to print Kth Character in the Nth row. Basically, we have to build a table of N rows. we will start by writing 0 in the first row, and now in every subsequent row will form using the previous row as replacing each occurrence of 0 with 01 and 1 with 10.
Example
Explanation - The row with N=3 will form like this.
0
01
0110
So the last row form is "0110" and we are asked the second character so it is 1.
Recursive Approach
One way is you can construct N rows in form of a list of lists using an iterative approach but we have to solve it efficiently so think of a recursive solution to this problem. You only need a few observation skills in this case So, if you observe the above example or any Nth row example then we can say that every subsequent row formed is half the same as the previous row and the remaining elements are just the complement of the previous row.
We can see that the first row has 1 character, the second row has 2 characters, the third has four characters, and so on so if you observe then the total number of characters in the Nth row is power(2, n-1). Now understand the complement concept so when we form 3rd row, we look at the second row which is 01 now write 01 as it is in the third row and its complement as 10 so the third row is 0110. If we form the fourth row then it is 01101001. So we can say that the Kth character in the Nth row will be the same as of N-1 row Kth character if K is less than half of the length of the formed string else It will complement of N-1th row kth character. What is the base case? We know that the first row is always zero so if N or K is 1 then output is 0.
💻 Code ~ Now you should write the code after this explanation or again read the explanation once.
def findKSymbol(n, k):
if n==1 or k==1:
return 0
mid = pow(2, n-1) // 2
#if k is in first half
if k <= mid:
return findKSymbol(n-1, k)
#else complement of n-1, kth character
else:
return not findKSymbol(n-1, k-mid)
n, k = 3, 2
if findKSymbol(n, k):
print(1)
else:
print(0)
2) Generate All Balance Parenthesis
Given N pairs of parenthesis, the task is to generate all combinations of valid parenthesis. It means that we are given a single integer as input and our task is to use the N number of opening and closing parenthesis to form all valid combinations.
Example
Explanation
There are all the valid combinations we can form using 3 opening and 3 closing parenthesis.
Recursive Approach
Use pen-paper, and try developing its binary tree of the above example. So if we have N number of opening and closing parenthesis, and we start forming a tree so each time we have two choices like to select one opening and one closing. So each time we move on we have two choices so we choose first open till we have an open or the remaining number of closing brackets are not greater than opening because we have to form a valid combination. observe the below binary tree for detailed clarification.
So we can conclude it like we use opening bracket till it is not zero or we use closing bracket only when a number of the opening is less than a remaining number of closing brackets and we get one combination when both numbers become zero. So let's write the code using this approach.
💻 Code
def BalanceParenthesis(opn, close, output, res):
if opn == 0 and close == 0:
res.append(output)
return
if opn != 0:
op1 = output + "("
BalanceParenthesis(opn-1, close, op1, res)
if close > opn:
op2 = output + ")"
BalanceParenthesis(opn, close-1, op2, res)
def main(n):
global res
res = []
opn = n
close = n
BalanceParenthesis(opn, close, "", res)
print(res)
n = int(input())
main(n)
3) Gray Code
One more interesting problem is the Gray code from Leetcode. The problem statement is something like we are given a decimal number ad task is to find the Gray code of number N and return it in decimal form. In simple words, the n-bit gray code sequence is a sequence of 2n integers which satisfy the following conditions.
- Every integer is in the inclusive range of [0, 2n - 1] where the first integer is always 0.
- The same integer does not appear more than once in a sequence.
- The binary representation of every pair of adjacent integers differs by exactly one bit. And the binary representation of the first and last integer should also differ by exactly one bit.
What we understand from the problem statement is we are given a decimal number and we have to find all possible binary code representations of that length and every subsequent code should only differ by one bit and return all code again in decimal format. Now let's take one example.
Example
Input = 2
Output = [0, 1, 3, 2]
Explanation
All binary representation formed is [00, 01, 11, 10]. Now you can check that each subsequent differ by exactly one bit.
- 00 and 01 differ by 1 bit
- 01 and 11 differ by 1 bit
- 11 and 10 differ by 1 bit
- 10 and 00 again differ by 1 bit
Recursive Approach
we have to find the N length of all possible binary bit combinations. So you only need observation skills in any sequence problem. here we have to arrange binary code in such a form that the next code only differs by one bit. So think when we have N equals 1 then the result is 0 and 1. Now we have to think about how we can prepare the second order from this combination. So by placing 0 before each combination once and then placing 1 before each combination we can obtain all four combinations for 2. But here is a small problem. If I form this combination then it will be [00, 01, 10, 11]. In this combination 01 and 10 differs by 2 bit. So what we do is first we place 0 before all combinations and to place 1 we use the reverse approach means we will place 1 before all combinations in reverse order.
So for 1, we have 0 and 1. Now for 2 first place 0 before both so we have 00 and 01. Now to place one we use a reverse combination so first place one before 1 and then before 0 so it forms 11 and 10 and the resultant combination is [00, 01, 11, 10]. Observe the below example for N equals 3.
💻 Now let's write the code for this problem.
def FindGrayCodes(n):
if n == 1:
return ["0", "1"]
currCode = FindGrayCodes(n-1)
res = []
#add 0 before each combination and add to result list
for i in range(len(currCode)):
s = currCode[i]
res.append("0" + s)
#add 1 bfore each combination from reverse
for i in range(len(currCode)-1, -1, -1):
s = currCode[i]
res.append("1" + s)
return res
def main(n):
res = FindGrayCodes(n)
#convert each combination to int and print corresponding decimal
fres = []
for i in res:
fres.append(int(i, 2))
print(*fres) #print all combination space-separated
n = int(input())
main(n)
4) Find the Maximum Number possible by doing at most K swaps
It is one Hard level question that will enforce you to think a little bit more deeply. Now at this point, we are capable we can think about its approach. So the problem statement is given a positive integer, our task is to find the maximum integer possible by doing K number of swaps of integer.
Example
Explanation
In the first case, we have a total 4 number of swaps so we can swap the first digit with the maximum number as 7 and the second with the second-largest, and so on. Same done in case 2 but some might be thinking like the maximum number formed is 4310 😀. So we only have 2 swaps in which 1 is swapped with 4 and 0 with 3 so we left by 4301.
Recursive Approach
Here we cannot do this by swapping the first digit with the largest digit and the second with the second-largest because always given integer will not be in this form so we have to check for each and every possible case. So how we will approach it in recursion is we will develop a recursive binary tree in which every time what choices we have to build the sub-branch. The first choice is to now do the swap and keep the digit as it is, another choice is to swap the first position digit with every other digit and then travel recursively till the value of K becomes zero and increase the position. Observe the below tree for one example and you will get the approach pretty clear.
Now let's get to IDE and implement this approach.
def swap(st, i, idx):
temp = list(st)
temp[i], temp[idx] = temp[idx], temp[i]
st = ''.join(temp)
return st
def helper(mx, st, k, idx, res):
#base case
if k == 0 or idx >= len(st):
return
n = len(st)
maxch = st[idx]
for i in range(idx+1, n):
if maxch < st[i]:
maxch = st[i]
if maxch != st[idx]: #If another then ch at idx we got mx then swap possible
k = k-1
for i in range(idx, n):
if st[i] == maxch:
#swap ch at i and idx
st = swap(st, i, idx)
#check if new formed st is greater then curr one
if st > mx:
mx = st
helper(mx, st, k, idx+1, res)
st = swap(st, i, idx)
res.append(mx)
def main(st, k, res):
mx = st
helper(mx, st, k, 0, res)
print(max(res))
global res
res = []
st = "1234567"
k = 4
main(st, k, res)
Practice Questions for You
A] Family Structure
This problem statement is based on the first question we have solved in this article so you must perform it in a short span of time.
Problem statement ~ Rahul is a member of the crazy-techie community. He has a weird family structure like every Male member gives birth to a male child first and then a female child. And every female member gives birth to a female member first and then to a male child. Rahul analyses this pattern and he wants to know the Kth child gender in Nth Generation. You as a programmer need to help Rahul.
The generation Tree always starts with a Male member means a first-generation male is there. So your task is to develop an algorithm that returns the gender of the Kth child of the Nth generation. The sample generation tree is shown below.
Example
Now you have to think about how you can use the first question as a reference and solve this question.
End Notes
We have covered the recursion question from the Hard category in this article. And now I assure you that after completing three parts on recursion and doing this many questions you are capable enough to think and build a recursive approach. So you can practice more recursion problems confidently on any coding site. From our next article in the competitive programming series, we will start Backtracking and will explore it in more depth because it is interconnected or the approach is built on Top of recursion only.
Thanks for your time! 😊