Must know Tips and Tricks for Competitive programming

Though competitive programming can only be mastered with lots of practice and consistent hard work, there are certain practices and tricks which can be your friend in this journey. Here you will see some good tips and tricks of the C++ programming language which will just help you to save a little time during the contests which might sometimes matter a lot.

1. Inbuilt GCD function:

C++ has an inbuilt GCD function and there is no need to explicitly code it. This seriously saves a lot of time during programming contests.

Syntax: __gcd(x, y);

Return Value : 0 if both m and n are zero,
else gcd of m and n.

2. A single header file to rule them all

There are so many header files which you need to include in your programs like algorithm, iostream, vector etc. But we can avoid writing all of them separately. We use a single header file :

#include <bits/stdc++.h>
This library includes many of the libraries we do need in contests like algorithm, iostream, vector, and many more. You don’t need to include anything else.

3. Count set bits in a number

__builtin_popcount(x) is a builtin function in GCC compiler.It returns number of 1s (set bits) in the integer variable x.

e.g. __builtin_popcount(14) = 3 because 14 is ‘… 111 0’ and has three 1-bits.

Similarly you can use __builtin_popcountl(x) & __builtin_popcountll(x) for long and long long data types.

4. endl vs /n

Using “\n” for adding new line breaks is much faster than using “endl” and can sometimes save you a TLE (Time Limit Exceeded) error during a programming contest.

5. Parsing input using stringstream

A stringstream class in C++ is a Stream Class to operate on strings. A stringstream associates a string object with a stream allowing you to read from the string as if it were a stream (like cin).
It has very important applications in programming like :

1. Extract individual words from a sentence or paragraph.
2. String to number conversion

and many more.

I have a separate post on stringstream and its applications. Check it out here:

=> stringstream in C++ : Detailed Usage and Applications with Examples

6. auto keyword

Using the auto keyword to declare data types can save a lot of time during programming contests.
When a variable is defined as auto, the compiler can determine its data type on its own.
Example:

auto var1 = 500; // a will become ‘int’
auto var2 = 1LL; // b will become ‘long long’

7. Range based for loop

set<int> s = {10, 22, 30, 11};

To traverse all the elements of set you would write something like this

for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
cout << *it << ‘ ‘;

C++ 11 introduced range-based for loop and if we combine it with the auto keyword we can simply iterate any container like this :

for (auto it: s)
cout << it << ‘ ‘;

8. Calculating the number of digits:

We can use a logarithm instead of looping to find out the number of digits in a number.
Number_of_digits_in_N = floor(log10(N)) + 1;

9. Fast Input/ Output in C++

It is often recommended to use scanf/printf instead of cin/cout for faster input and output. However, you can still use cin/cout and achieve the same speed as scanf/printf by including the following two lines in the beginning of your main() function( before you take any input) :
ios_base::sync_with_stdio(false);
cin.tie(NULL);

Note : If you use this fast I/O technique, you’ll no longer be able to use printf or scanf in your program.

10. Using typedef and #define

Using typedef’s for providing shorter names to different data types saves a lot of time in declaring variables in your program. You can directly use these shorter names for declaring variables.

typedef long long ll;
typedef pair pp;
typedef vector vec;

Eg. we can declare a pair<int,int> simply as pp p = make_pair(4,5);

Another way to shorten code is to define macros. A macro means that certain parts of the code will be changed before the compilation. macros are defined using the #define keyword.
For example, we can define the following macros:

#define F first;
#define S second;
#define pb push_back;
#define mp make_pair;

Now you can make a pair<int,int> in C++ as pp p = mp(4,5);

We can access the members of p by writing cout<<p.F<<” “<<p.S<<”\n”;

11. Assign value by a pair of {} to a container

braces {} can be used to initialize various containers like pair, vector, deque, etc very easily as shown below.

a.
pair<int, int> p;
Instead of : p = make_pair(3, 4);
you can just do this: p = {3, 4};

b. Initialize a vector as
vector<int> v;
v = {1, 2, 5, 2};

c. Initialize a set as
set<int> s;
s = {4, 6, 2, 7, 4};

12. More powerful set container : ordered_set

An ordered set is a policy-based data structure in g++ that keeps elements in sorted order. It performs all the operations as performed by the set data structure in STL(like find(), lower_bound() etc.) in O(log(n)) complexity and performs two additional functions with the same O(log(n)) complexity:

order_of_key (k): number of items which are strictly smaller than k .
find_by_order(k) : k-th element in a set (counting from zero).

I have a separate detailed post on ordered_set and its applications. Check it out here:

=> Ordered Set in C++ : Policy-Based Data Structure

13. inbuilt binary search

C++ STL provides us two functions which implement binary search for us, we just need to provide the value and the function automatically uses binary search to find iterator to the specified value in O(nlog n)

a. Iterator lower_bound (Iterator first, Iterator last, const val)

lower_bound returns an iterator pointing to the first element in the range [first, last) which has a value not less than ‘val’.

b. Iterator upper_bound (Iterator first, Iterator last, const val)

upper_bound returns an iterator pointing to the first element in the range [first, last) which has a value greater than ‘val’.

14. Inbuilt sort

Sorting is one of the most basic functions applied in many programming problems.
There is a built-in function in C++ STL by the name of sort().

Syntax:
sort(startaddress, endaddress)

startaddress: the address of the first element of the array
endaddress: the address of the next contiguous location of the last element of the array.

int a[10]= {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

sort(a, a+10);

//We can use sort for vector using iterators;

vector<int> vec = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
sort(vec.begin(), vec.end());

15. string as stack : pushback() and popback()

If you want to apply stack-like functionality using string, you don’t need to explicitly declare a stack of characters as a string in C++ automatically provides that functionality but very few people are actually aware of this thing.

string s = “codingwithart”;
s.push_back(‘N’); // pushes a new character at the end of string, s = “codingwithartN”
s.pop_back(); // pops the last character from the string, s = “codingwithart”

16. Bit manipulation using bitset

Using bitwise operators on multiple numbers can be a bit tricky. Therefore C++ provides us with bitset to carefully work on arrays of numbers.
A bitset is an array of bool but each bool value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] or vector bs(N). bitset provides us with a variety of predefined functions like count, size, set, reset, and many more.
However, a limitation of bitset is, N must be known at compile-time, i.e., a constant

For example :

bitset<8> set8; // 00000000

// setting first bit (or 6th index)

set8[1] = 1; // 00000010
cout << set8 << endl;

// count function returns number of set bits in bitset

int numberof1 = set8.count();

// size function returns total number of bits in bitset
// so there difference will give us number of unset(0)
// bits in bitset

int numberof0 = set8.size() — numberof1;
// bset.set(pos, b) makes bset[pos] = b
cout << set8.set(4, 0) << endl;

17. Initialize using memset()

We can use memset() to set all values as 0 or -1 for integral data types. It will not work if we use it to set other values. It works for both 1D and 2D arrays.

Example :
int a[5][5];

// all elements of A are zero
memset(a, 0, sizeof(a));

We can also use this for strings to set all characters as a particular character :

char str[] = “CodingWithArt”;
memset(str, ‘w’, sizeof(str));
cout << str;
return 0;

Output :
wwwwwwwwwwwww

18. Functor in C++

You may have provided a separate custom compare function for sort() in C++. But you can also provide it for containers like set, priority_queue etc but in a different way, using functor in C++.

// Sort a set of pairs by second value by functor

#define pii pair<int,int>
struct comp
{
bool operator()(const pii &a, const pii &b)
{
return a.second<b.second;
}
};

set<pii,comp> s;

Now, whenever you insert some pair into this set, it will sort everything based on the second element primarily. Of course, you could swap the first and the second element and avoid the functor. In case there are cases where you need to do some complex sorting, the functor can be of great help.

19. Check if a number is a power of 2

A simple solution to this problem is to repeated divide N by 2 if N is even. If we end up with a 1 then N is the power of 2, otherwise not.
The time complexity of the above code is O(logN).

The same problem can be solved using bit manipulation.

Consider a number x. Now (x-1) will have all the bits the same as x, except for the rightmost 1 in x and all the bits to the right of the rightmost 1.

For example:

Let, x = 4 = (100)2
x — 1 = 3 = (011)2

Properties for numbers which are powers of 2, is that they have one and only one bit set in their binary representation. If the number is neither zero nor a power of two, it will have 1 in more than one place. So if x is a power of 2 then x & (x-1) will be 0.

bool isPowerOfTwo(int x)
{
// x will check if x == 0 and !(x & (x — 1)) will check if x is a power of 2 or not
return (x && !(x & (x — 1)));
}

20. Find Least significant bit of a number

You can get the LSB of a number using a single line of code:

int LSB = x&-x;

(-x) is the two’s complement of x. (-x) will be equal to one’s complement of x plus 1.
Therefore (-x) will have all the bits flipped that are on the left of the rightmost 1 in x. So x & (-x) will return rightmost 1.

For example :
x = 10 = (1010)2
(-x) = -10 = (0110)2
x & (-x) = (1010)2 & (0110)2 = (0010)2

This brings us to the end of this article. If you have any doubts please mention them in the comments section.

Thank you for your patience in reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend or sharing it on Whatsapp or Facebook.

Happy Learning!!