Thursday, 10 May 2018

Euler Totient Function

Hello Coders,

I am writing this blogpost after a very long time. I am really sorry for that. :(

This blogpost is related to a mathematical topic which is Euler Totient function and there are many problems which are based on this mathematical concept.

What is Euler Totient Function?
It is a function which takes the input an integer n and in return it gives the number of relatively prime numbers to n which are smaller than it.

Monday, 12 February 2018

Code Chef: February Challenge First Five

Chef And His Characters:

This problem is straight-forward. Check every substring of length four and find if the 4 characters of string are 'c', 'h', 'e' and 'f'.
Complexity: Linear per case.
Link to my C++ code!  

Monday, 15 January 2018

Code Chef january challenge unofficial editorial for first 5 problems

Rectangle:

This is the easiest problem of the contest. Opposite sides of a rectangle are equal. So use this property to see if there are 2 pairs of equal sides.

Monday, 1 January 2018

Longest increasing subsequence


Contents:

  1. Wtf is Longest increasing subsequence?
  2. Dynamic programming approach to find the length.
  3. O(nlog(n)) solution to find length using binary search.

Friday, 22 December 2017

Heaps and Priority Queue

Contents:

  1. Heaps and Priority Queue
  2. Types of Heap
    1. Min-heap
    2. Max-heap
  3.  Some uses of heap with their complexities.
  4.  Problem from Hackerearth:
    1. Brute Force solution
    2. Solution using priority_queue

Wednesday, 13 December 2017

Square Root Decomposition with range updates

Hello guys! Hope you all are doing well.
In Codechef December challenge I came across a very interesting problem which can be solved using square root decomposition. So i am gonna explain the algorithm using that particular problem. Link to problem.

Pre-requisites: properties of XOR operation.

Sunday, 10 December 2017

Lazy Propagation on segment tree

LAZY PROPAGATION

This is for the update query in the minimum range query question.The brute force method involves
various updates in the segment tree for just one query.However ,in lazy propogation,the update is
only propogated to the child nodes as and when it is required i.e. we maintain another array which
keeps the track of all the previous updates which have not been made yet in the segment tree and
will update only when there is a query on that particular range.

Saturday, 9 December 2017

Segment Trees and range minimum query

SEGMENTED TREES

We generally come across question involving range queries and update queries which may or may not require to print output after each queries.
For example:-we have an array arr[0.....n-1] and following two queries:
1.find minimum in range [l,r] where 0<l<r<n and output it.
2.upadate each value in range [l,r] and output the new array.

Friday, 20 October 2017

Selection Sort


Hey Everyone !
In this article i am going to describe the Selection Sort Algorithm which has a complexity of O(n^2) and people don't prefer to use this algorithm in competitve programming contests, but i am writing this because it can be asked in viva or during exams in colleges.

Sunday, 6 August 2017

Z-Algorithm


Contents :
  • Objective of this post
  • An Awesome video tutorial on You Tube
  • Implementation in C++
  • Practice Problems

Thursday, 27 July 2017

All about Trie data structure !


Contents :
  1. Introduction to Trie
  2. Insertion of a string in Trie
  3. Searching a string in a Trie
  4. Application : Auto-Complete the keyword

Thursday, 20 July 2017

Understanding Binary Search and Linear Search


Contents :
  • Understanding Linear search and its time complexity
  • Understanding Binary search
  • Implementation of binary search in C++

Wednesday, 19 July 2017

Merge Sort Algorithm


Merge Sort Algorithm is a sorting algorithm which has time complexity of O(nlog(n)) where n is number of elements in the unsorted list. In merge sort algorithm we divide the array in two halves and then sort those

Tuesday, 11 July 2017

Breadth First Search in C++


Prerequisites : Adjacency List, Queue data structure(FIFO)
Breadth First Search :
Like DFS, BFS is another form of Graph traversal Algorithm. Instead of going deeper and deeper, unlike DFS it goes in breadth first faishon which means that if it is on node u currently, then it first visits all the neighbours of node u and then the same thing happens with each of its neighbours. Lets understand how this algorithm works with the help of an example.

Monday, 10 July 2017

Topological sort on a directed acyclic graph


Contents:
  1. What is Topological Sorting ?
  2. Illustration with the help of an example.
  3. Implementation of topological sort in C++.

Finding connected Components using DFS in C++


Contents :
  1. Pre-requisites
  2. Understanding connected components.
  3. Implementing DFS to find number of connected components.

Depth First Search in C++


Hey Guys ! Hope you are doing well !
In my previous post i wrote about implementation of Adjacency List in C++. So if you don't know how to implement Adjacency List in C++, you must read this post.

Depth First Search

DFS (in short) is a simple algorithm to traverse a graph.

Tuesday, 4 July 2017

Graph : Adjacency List using STL in C++ for competitve programming


CONTENTS :
  1. Introduction to Adjacency List.
  2. Some STL Componenets required to make Adjacency List:
    • Vector
    • Pair
    • Map
  3. Implementation in C++.

Tuesday, 13 June 2017

Featured Posts

Euler Totient Function

Hello Coders, I am writing this blogpost after a very long time. I am really sorry for that. :( This blogpost is related to a mathemat...