Must Know Algorithmic Tricks for Competitive Programming

Some Tips and Strategies for Solving Challenging Problems

Competitive programming is a sport that requires speed, accuracy, and creativity. To excel in this field, one needs to have a deep understanding of algorithms, data structures, and problem-solving strategies. In this article, we will explore some must-know algorithmic tricks that can help you improve your competitive programming skills and solve complex problems with ease.


Modular Arithmetic

In modular arithmetic, all calculations are performed modulo a given number. This is useful for problems that involve working with large numbers or computing remainders. Java provides the modulo operator (%) for performing modular arithmetic, but this can be slow for large numbers. A faster approach is to use the fact that (a + b) % p = (a % p + b % p) % p and (a * b) % p = (a % p * b % p) % p, where p is the modulus. For example, you can use the following code to calculate a^b % p efficiently:

long power = 1;
while (b > 0) {
    if (b % 2 == 1) {
        power = (power * a) % p;
    }
    a = (a * a) % p;
    b /= 2;
}

Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number, starting from 2. After all multiples have been marked, the unmarked numbers are prime. This algorithm can be implemented efficiently in Java using an array to keep track of the prime numbers. For example, you can use the following code to generate all prime numbers up to a given limit:

int n = Integer.parseInt(br.readLine());
boolean[] isPrime = new boolean[n+1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
        primes.add(i);
    }
}

Use of BitSet

The BitSet class in Java can be used to represent a set of bits, where each bit is either 0 or 1. It provides fast bitwise operations such as AND, OR, XOR, and NOT. BitSet is particularly useful for problems that involve manipulating large sets of binary values efficiently. For example, you can use the following code to count the number of 1-bits in an integer:

int n = Integer.parseInt(br.readLine());
BitSet bs = BitSet.valueOf(new long[]{n});
int count = bs.cardinality(); // number of 1-bits

Euler’s method for finding the greatest common divisor (GCD) of two integers

The Euclidean algorithm is a well-known method for finding the greatest common divisor (GCD) of two integers. However, there is another method for finding the GCD of two numbers, known as the Euler’s method. Here is how it works:

Let a and b be two integers with a > b. We can write a as a multiple of b plus a remainder, i.e., a = bq + r, where 0 <= r < b. Now, if d is a common divisor of a and b, then it must also divide r (because d divides both a and b, so it must also divide a – bq = r).

Conversely, if d is a common divisor of b and r, then it must also divide a (because a = bq + r, and d divides both b and r, so it must also divide their sum). Therefore, we can use the following recurrence to find the GCD of a and b:

gcd(a, b) = gcd(b, r)

We can repeat this process until the remainder r is 0, at which point the GCD of a and b is equal to b (since any divisor of b must also divide a).

here is an implementation using the Euler’s method:

public static int gcd(int a, int b) {
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }
    while (b > 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return b;
}

Find most significant digit of any number using log

To find the most significant digit of a positive integer n, we can use the fact that the number of digits in n is given by floor(log10(n)) + 1. For example, if n = 123456789, then the number of digits in n is floor(log10(123456789)) + 1 = 9.

To find the most significant digit of n, we can use the formula:

msd(n) = floor(n / 10^(floor(log10(n))))

The expression floor(n / 10^(floor(log10(n)))) calculates the integer part of the division of n by 10 to the power of the number of digits in n minus 1 (i.e., the number formed by the first digit of n).

Here is a Java method that implements this algorithm:

public static int mostSignificantDigit(int n) {
    int numDigits = (int)Math.floor(Math.log10(n)) + 1;
    int divisor = (int)Math.pow(10, numDigits - 1);
    return (int)Math.floor(n / divisor);
}

Note that this method assumes that n is a positive integer. If n can be negative, you can use the absolute value of n (i.e., Math.abs(n)) to calculate the most significant digit, and then multiply the result by -1 if n was originally negative.


Fast multiplication algorithms

One common fast multiplication algorithm is the Karatsuba algorithm, which uses a recursive divide-and-conquer approach to reduce the number of individual multiplications required. The Karatsuba algorithm has a time complexity of O(n^log_2(3)), which is faster than the O(n^2) time complexity of the schoolbook method for large values of n.

Here is an example implementation of the Karatsuba algorithm in Java:

public static BigInteger karatsuba(BigInteger x, BigInteger y) {
    int n = Math.max(x.bitLength(), y.bitLength());
    if (n <= 2000) {
        return x.multiply(y);
    }
    n = (n / 2) + (n % 2);
    BigInteger b = x.shiftRight(n);
    BigInteger a = x.subtract(b.shiftLeft(n));
    BigInteger d = y.shiftRight(n);
    BigInteger c = y.subtract(d.shiftLeft(n));
    BigInteger ac = karatsuba(a, c);
    BigInteger bd = karatsuba(b, d);
    BigInteger abcd = karatsuba(a.add(b), c.add(d));
    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(n)).add(bd.shiftLeft(2*n));
}

In conclusion, competitive programming is a challenging yet rewarding field that requires continuous learning and practice. By mastering these advanced algorithmic tricks you can enhance your problem-solving skills and become a more competitive programmer. Keep exploring new ideas and techniques, and always stay curious and motivated!

Read more DSA Blogs

Blogs on medium