Competitive Python

A prime number is a number that is only divisible by 1 and the number itself. There are multiple ways we could test if a number is prime or not but today we will talk about two ways- Naive method sqrt(n) prime testing (the efficient method) The Naive method One method would be to check all possibilities from 2 to n - 1, n being the number we are testing. This would mean that if a number is prime we will have to search through all the numbers from 2 to n - 1. But if a number is not a prime then we will not have to search through all the possibilities, we will just return false if a number is completely divisible by another number that means it doesn't leave any remainder. def isPrime(n): for i in range(2,n): if n%i==0: return False return True The worst case for this method would be O(N). Sqrt(n) method Okay, so the logic behind this method is that every composite number has at least one factor that lies between 0 and the square root of n.

If you want to learn about Stack or Queue, follow the link to the tutorials- Queue Stack Questions- Maximum Element Equal Stacks Balanced brackets Simple Text Editor Queue using two stacks Castle on the grid Stock Span Problem Celebrity Problem Next greater element

Today, we will talk about another linear data structure , a Queue. It is a data structure thay basically acts like a real life queue. It works on FIFO (First in First out) principle. It means that the element that gets added to the queue first gets removed the first, it's like first come first serve basis.In a queue, the operations take effect at rear and front end of the list. Enque adds the element to the back of the queue and Dequeue removes the element from the front of the queue. Queue is a very essential data structure and also form the basis for some advanced data structures. Applications of a queue- CPU procces scheduling Real life simulations The methods associated with a queue are - Enque(): Adds an element to the back of the queue Deque(): Removes an element from the front of the queue isEmpty(): Returns wether the queue is empty or not size(): Returns the size of the queue Here is the implementation of the Queue data structure, in this implementation we

Stack So, now we're going to talk about stack , a linear data structure and also we will see its implementation. In another post which will be linked below later will discuss its uses. So what is a stack ? Visualise a pile of coins or a stack of trays put one over the other. The item that has been put at the last has to be removed first as it is over all the other items. Hence, it is a data structure that works on LIFO (Last in First out) principle. Which simply means that the element that has been added the last will be removed first. It is a very useful data structure and has several applications like expression evaluation and HTML validat or or a bracket matching verifier . In this data structure we only have operations that take their effect only at one end of the list. Both, the front or the end of a list can be used to implement it but using the tail(back-end) of the list is more efficient. The main operation or methods on a stack are - Push : Adds element at the

Sorting Why do we need to sort? Merge Sort Quick Sort Why do we need to sort? Sorting is among the most important, and well studied, of computing problems. Python does have a built in method for sorting a collection but it is very advance and highly optimised, it's known as timsort , even java's inbuilt sorting method uses this algorithm. A programmer should usually depend on built-in sorting functions than rolling out a search algorithm from scratch. But with that being said it is still imperative to have a deep understanding of how sorting algorithms functions as it makes you more and more aware about your program in terms of efficiency and space complexity We will see and study two of the quicker sorting algorithms, mergesort and quicksort .Both these algorithms work on divide and conquer design pattern. Merge Sort Merge sort is a recursive algorithm.It works by splitting the list into half and then calling mergesort on both the halves independently. Once the two

Binary Search Okay, so how do you think we can search for a paticular element in an array? One obvious way will be to loop through the array and return true at which the element is found and to return false if it doesn't exist in the array. But the problem with this algorithm known as linear search is that it can very quickly turn out to be very costly in terms of space and time as this algorithm takes O(n) or linear time. This turns out to be highly costly for a large number of elements in an array. #Linear Search --> def linear_search(array , n ): for i in array: if i == n : return True So, the solution to this is to use an algorithm called binary search . Binary search is an algorithm that works on the divide and conquer technique and is also extremely efficient.It works on O(logn). But the only catch to this algorithm is that the array it is being applied on needs to be sorted . #Binary Search --> def binary_search(array, n ): #Setting up search

Recursion What is recursion Three rules of recursion Examples Fibonacci Factorial Additional Resources What is recursion? Recursion is a method of solving problems based on divide and conquer.It is a very elegant way to write solutions to problems that would be pretty inefficient in an iterative solution ( using loops ). A recursive function is basically a function that calls itself on a problem that is somehow smaller or more simplified than the original problem . For example see the function sum of list #Iterative Solution---> 1)def listSum( list ) : 2) sum = 0 3) for i in list : 4) sum += i 5) return sum 1)def listSum( list ) : 2) if len( list ) == 1 : 3) return list[0] 4) else : 5) return list[0] + listSum(list[1:]) In the iterative solution we go through each item in the list and keep adding it to the sum variable . But the same can be solved using a recursive solution . First, in line 2 we check for the base case,that is if the list is