Top 10 helpful programs

Aadil Mugal

Posted on 12 jul 2022

C++Competitive ProgrammingProblem Solving

Here are 10 most helpful program code snippets that I use during coding contest which can be used as subroutine

1. Quickly check odd or even

1bool isOdd(int n){
2	return n&1;
3}

cpp

2. Count digits in an integer

1int countDigit(int n) { 
2  return floor(log10(n) + 1); 
3}

cpp

3. Greatest common Divisor by Euclid's Algorithm

1int gcd(int a, int b) {
2    return b ? gcd(b, a % b) : a;
3}

cpp

4. Exponential Squaring with mod

1#define MOD 1000000007 // prime modulo value
2
3long long  fast_exp(int base, int exp)  {
4    long long res = 1;
5    while (exp > 0) {
6        if (exp % 2 == 1)
7            res = (res * base) % MOD;
8        base = (base * base) % MOD;
9        exp /= 2;
10    }
11    return res % MOD;
12}

cpp

This is useful when calculating very large powers. Usually the value of MOD is given in the question (used to avoid overflow).

5. Kadane’s Algorithm (Maximum Sum Subarray Problem)

1#include <climits>
2...
3
4int kadaneNeg(vector<int> const &arr) {
5    int max_so_far = INT_MIN;
6    int max_ending_here = 0;
7
8    for (int i = 1; i < arr.size(); i++) {
9        max_ending_here = max_ending_here + arr[i];
10        max_ending_here = max(max_ending_here, arr[i]);
11        max_so_far = max(max_so_far, max_ending_here);
12    }
13
14    return max_so_far;
15}

cpp

6. Fast Multiplication or Division by 2

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

cpp

7. Calculating the most significant digit

1#include <bits/stdc++.h>
2...
3int MSD(int n) {
4  if (n == 0)
5    return 0;
6  int k = log10(n);
7  int x = pow(10, k);
8  int ans = n / x;
9  return ans;
10}

cpp

8. To find whether a given number is power of 2

1bool isPowerOfTwo(int x){
2    if (x < 0) return false;
3    return x && (!(x & (x - 1)));
4}

cpp

9. C++11 has inbuilt algorithms for the following

1all_of(first, first + n, ispositive());
2any_of(first, first + n, ispositive());
3none_of(first, first + n, ispositive());

cpp

10. binary search Algorithm

1int binarySearch(int arr[], int p, int r, int num) {
2   if (p <= r) {
3      int mid = (p + r) / 2;
4      if (arr[mid] == num)
5         return mid ;
6      if (arr[mid] > num)
7         return binarySearch(arr, p, mid - 1, num);
8      if (arr[mid] < num)
9         return binarySearch(arr, mid + 1, r, num);
10   }
11   return -1;
12}

cpp