if (test for Base Case-I)
   return Base Case Value
elsif (test for Base Case-II)
   return Base Case Value II
Do something if needed
Make recursive call
Do Something if Need

Recursion Problems:

Sorting:
1. Merge Sort:

2. Quick Sort:

Binary Search:

Tree Traversals:

1. Inorder

2. Preorder

3. PostOrder

Graph Traversals

1. Breadth First Search

2. Depth First Search

Tower of Hanoi:

Explanation: http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/13/hanoi.html

It is a particular way to store and organize data in a computer so that it can be used efficiently. The data structure can be classified into two ways:

1. Linear data structure
2. Non-linear data structure

Abstract Data Types

User defined data structures combined with their operations are called Abstract Data types. It consists of two parts:
1. Declaration of data
2. Declaration of operations

Algorithm

The two criteria for algorithms:
1. Correctness — Does the algorithm give solution in finite number of steps?
2. Efficiency — Resources needed in terms of memory and time.
Comparison of Algorithm: Rate of growth

Big — O notation: Upper Bound running time
Big — Ω notation: Lower Bound running time (No practical importance)
Big — Θ notation: Average running time

Master Theorem

Question: https://codeforces.com/problemset/problem/1389/A

INSPECTION:

Find two integers x and y such that l≤x<y≤r and l≤LCM(x,y)≤r.let x=l
LCM(x,x*2) if x*2<=r is the smallest LCM(x,y).Trusting greedy,
  x,y=l,l*2

CODE

def solve(arr):
    [x,y]=arr
    if x*2>y:
        print(-1,-1)
    else:
        print(x,x*2)t= int(input())
for _ in range(t):
    arr= list(map(int, input().rstrip().split()))
    solve(arr)

Question : https://codeforces.com/problemset/problem/1337/A

Inspection:

1. High constraints. Looping (O (n³)) is not efficient.

The next t lines describe test cases. Each test case is given as four space-separated integers a, b, c, d (1≤a≤b≤c≤d≤10^9).

2. Rule of Triangle sides

X+Y>Z 

3. When they satisfy the rule of Triangles

Min X = a , Max X = b
Min Y = b , Max Y = c
Min(X+Y) = a+b , Max (X+Y) = b+c if there exists z such that c<= z<=d and z< Max(X+Y)
or c<=z<=Min(d,b+c-1)
=> Triangle exists. All z in this range is a valid one.

4. If a triangle exists, find the sides .

Assume z= Min(d,b+c-1)
x,y=b,c 
if z==d and d<b+c-1:
    z<x+y is True
else:
    z<x+y is True too

CODE

def solve(arr):
    [a,b,c,d]=arr
    z=min(d,b+c-1)
    print(b,c,z)t= int(input())
for _ in range(t):
    arr= list(map(int, input().rstrip().split()))
    solve(arr)

Question: https://leetcode.com/problems/count-primes/

INSPECTION

1. Nothing special in this problem. Sieve of Eratosthenes implementation.

SOLUTION

import math
class Solution:
    def countPrimes(self, n: int) -> int:
        
        if n<=1:
            return 0
        
        boolean_counter=[True for j in range(n+1)]
        boolean_counter[0],boolean_counter[1]=False,False
        for i in range(2,int(math.sqrt(n))+1):
            if (boolean_counter[i]==True and i*i<=n):
                for j in range(i*i,n+1,i):
                    boolean_counter[j]=False
        prime_count=0
        for i in range(2,n):
            if boolean_counter[i]:
                prime_count+=1
        return prime_count