Skip to main content

MATHS

To become good at competitive programming, it is required that you have an understanding of the most useful mathematical concepts and some common operations and operators. If you think you can escape from Maths you will definitely not perform too good, that being said the concepts discussed here is relatively easy, with some effort you can go a long way.

Caution

You already might be knowing about some or all of these, but I recommend you not to skip because here is a complete coverage on the important topics including the most optimised approaches of performing the crucial tasks. It will be an opportunity for you not just to revise but also to gain the complete knowledge of what is most useful and fundamental in competitive programming.

Time Complexity#

The Time Complexity analysis is the most basic of concepts that you will be using throughout your programming career and it will help you judge the performance of your code. Understand the basics here, you will develop a deeper understanding of analysing time complexity as you learn more about various algorithms and practice more questions.

Remainder and Quotient#

Two of the most used operators and basic maths operation, the remainder ‘%’ or the modulo operator gives the remainder when any number a is divided by number b. The ‘ / ‘ or the quotient operator gives the quotient when number a is divided by number b.

Bit Manipulation#

Bitwise Operators though very trivial but then again they are very fast operations faster than basic addition, subtraction operations and very useful. Some of the advanced algorithms and data structures that you will learn later work because they could rely on bitwise operators for doing their operations.

Greatest Common Divisor aka GCD#

Nothing great about Greatest Common Divisor aka GCD, you must already know about it, but wait, can you solve the problems? Did you know that the best time complexity of finding GCD is O(logN). Can you prove it? Did you know about the inbuilt GCD in C++. Well read on, there is lots of basics to learn.

Tips

Use the inbuilt GCD method to avoid mistakes, save time and speed up your algorithm.

Calculating Power#

Well even a class 6 student knows how to write a program to find the power of a number raised to another number, but does he know how to do it in logarithmic time complexity, you are about to learn to do exactly that. Logarithmic time is the fastest you could be to calculate the power of one number raised to another, it is pretty cool considering that given large inputs it is expected of you to calculate the power in logarithmic time or else you will hit a Time Limit Exceeded error. Do understand thoroughly the concept of Binary Exponentiation and remember how it works in helping you find the power in logarithmic time.

Permutation and Combination#

Inclusion Exclusion Principle#

Euler Totient Function#

Now this is something not taught to you in school but something that you will learn when solving coding problem where you need to find the modular multiplicative inverse of a number. So what is this function and why is it important and where is it used? If you want to find out, what are you waiting for, deep dive into this wonderful article. Post reading this article you should have a clear understanding of the Euler Totient function.

RESOURCES

Prime Factorization#

QUESTION

Sieve of Eratosthenes aka SOE#

In brief, this algorithm wil enable you to find all the prime numbers in a range from 1 to n, now this is not the noteworthy point here, the point to note is that it enables you to do so in O(Nlog(logN)). This algorithm will save your solution from TLE in a lot many questions, read in depth about this useful approach. The proof of the time complexity is a little complex and not needed, it suffices just to know the time complexity.

Caution

The concept of Segmented SOE is a slightly advanced topic and not recommended if you are preparing for any company interview but in case if you are gearing up for top ranks in competitive programming it is a must know concept.

Concept of Modulo#

As a simple trick to make your life difficult and the problems more challenging you will be given larger inputs, as a competitive programming enthusiast you must know how to deal with such scenarios and modulo is something that will come to your aid, so read and understand to use the concept of modulo properly.

Modular Multiplicative Inverse#

As mentioned earlier in many problems you will be doing modulo operations, it is only natural that you will encounter cases where finding the modulo can be a little tricky, one such case is that of modular multiplicative inverse, this tiny little hiccup can be easily overcome if only you know how to, read on about what it is and how to calculate it.

Random#