C++ tricks for competitive programming

1) Checking if the number is even or odd without using the % operator:

Although this trick is not much better than using % operator but is sometimes efficient (with large numbers).
Use & operator:

if (num & 1) 
cout << "ODD";
cout << "EVEN";

num = 5
Binary: “101 & 1” will be 001, so true
num = 4
Binary: “100 & 1” will be 000, so false.

2) Fast Multiplication or Division by 2

Multiplying by 2 means shifting all the bits to left and dividing by 2 means shifting to the right.
Example : 2 (Binary 10): shifting left 4 (Binary 100) and right 1 (Binary 1)

n = n << 1;   // Multiply n with 2 
n = n >> 1; // Divide n by 2

3) Swapping of 2 numbers using XOR:

This method is fast and doesn’t require the use of 3rd variable.

// A quick way to swap a and b 
a ^= b;
b ^= a;
a ^= b;

4) Avoiding use of strlen():

//  Use of strlen() can be avoided by: 
for (i=0; s[i]; i++)
// loop breaks when the character array ends.

5) Calculating the most significant digit:

To calculate the most significant digit of any number log can be directly used to calculate it.

Suppose the number is N then 
Let double K = log10(N);
now K = K - floor(K);
int X = pow(10, K);
X will be the most significant digit.

6) Calculating the most significant digit:

To calculate number of digits in a number, instead of looping you can efficiently use log :

Number of digits in N =floor(log10(N)) + 1;

7) Get rid of those includes!

Simply Use

#include <bits/stdc++.h>

This library includes many of libraries we do need in contest like algorithm, iostream, vector and many more. Believe me you don't need to include anything else!

8) Calculating the GCD

To calculate the gcd use the following builtin function

GCD=__gcd(value1, value2);

9) Lambda expression in C++

C++ 11 introduced lambda expression to allow us write an inline function which can be used for short snippets of code that are not going to be reuse and not worth naming. In its simplest form lambda expression can be defined as follows:

[ capture clause ] (parameters) -> return-type  
definition of method

10) Auto Keyword in C++

In C++ you can use auto to iterate over map,vector,set,..etc which specifies that the type of the variable that is being declared will be automatically deduced from its initializer or for functions it will the return type or it will be deduced from its return statements

So instead of :

vector vs;
for (vector::iterator it = vs.begin(); it != vs.end(); ++it)
cout << *it << ' ';cout<<'\n';

just use :

vector vs;
for (auto it: vs)
cout << it << ' ';cout< vs;
for (auto& it: vs) it*=3;
for (auto it: vs)

Post a Comment

Post a Comment (0)

Previous Post Next Post