Math Tricks in Competitive Programming

Competitive programming is not just about knowing programming syntax—it’s a blend of logic, speed, and mathematics. Mastering a few essential math tricks can drastically boost your problem-solving skills and efficiency.

Let’s explore the most powerful and commonly used math techniques in competitive programming.

Number of times a prime p exist in n!

count_of_p = n//p + n//p^2 + n//p^3........

count_of_p = n//p + n//p^2 + n//p^3........

Example find no. of trailing zero in 100!

• Zero is formed by 2*5

no_of_2 = 100/2 +100//4 + 100//8 + 100/16 + 100/32 + 100/64 + 100/128
        = 50 + 25 + 12 + 6 + 3 + 1 + 0 .....
        = 97

no_of_2 = 100/2 +100//4 + 100//8 + 100/16 + 100/32 + 100/64 + 100/128
        = 50 + 25 + 12 + 6 + 3 + 1 + 0 .....
        = 97

no_of_5 = 100//5 + 100//25 + 100//125
        = 20 + 4 + 0
        = 24

no_of_5 = 100//5 + 100//25 + 100//125
        = 20 + 4 + 0
        = 24

So, no of zero min(no_of_2,no_of_5) = 24

Compute: a^b

Naive Method:

def power(a, b):
    result = 1
    for _ in range(b):
        result *= a
    return result

def power(a, b):
    result = 1
    for _ in range(b):
        result *= a
    return result

• Multiplying a , b times
• It become, inefficient especially when b is large.
• Time Complexity: O(b) => O(n)

Fast Exponentiation Idea

Reduce the number of multiplications by squaring instead of multiplying a again and again.

Example: a^8

• a^8 = (a^4)^2 = ((a^2)^2)^2
• Instead of multiplying a 8 times, you just square 3 times!

2^10 => 4^5 => 
4^5 => 4^(4+1) => 16^2 * 4^1

2^10 => 4^5 => 
4^5 => 4^(4+1) => 16^2 * 4^1

• Using above representation of the exponent, it reduces the time to O(log b).

Code

def fast_pow(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:      # if current bit is 1
            result *= a
        a *= a              # square the base
        b //= 2             # move to next bit
    return result

def fast_pow(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:      # if current bit is 1
            result *= a
        a *= a              # square the base
        b //= 2             # move to next bit
    return result

Key concept:

• In every loop we square ‘a‘ (a^2) while reduces b by half
• When b is odd, we multiple ‘a’ once

Special case b is negative

def fast_pow(a, b):
    if b == 0:
        return 1
    if b < 0:
        return 1 / fast_pow(a, -b)  # invert the result

    result = 1
    while b > 0:
        if b % 2 == 1:
            result = result * a
        a = a * a
        b = b // 2
    return result

def fast_pow(a, b):
    if b == 0:
        return 1
    if b < 0:
        return 1 / fast_pow(a, -b)  # invert the result

    result = 1
    while b > 0:
        if b % 2 == 1:
            result = result * a
        a = a * a
        b = b // 2
    return result

Note :

• 1 / fast_pow(a, -b), we passing -b
• a^(-b) = 1 / (a^b)
• Example 2^(-3) = 1 / (2^3) = 1 / 8 = 0.125

Why This Is Better Than a Loop:

• A regular loop takes b steps.
• Fast exponentiation takes only log₂(b) steps.

For example:

• If b = 1_000_000_000, loop = 1 billion steps
• Fast exponentiation = only 30 steps

Practice

• Leetcode 50

Logarithm

Definition: b^c = a ⇔ log_b(a) = c

Log of 1: log_b(1) = 0 ⇔ b⁰ = 1

Log of base: log_b(b) = 1 ⇔ b¹ = b

Log of power: log_b(aⁿ) = n · log_b(a)

Product Rule: log_b(x · y) = log_b(x) + log_b(y)

Quotient Rule: log_b(x / y) = log_b(x) – log_b(y)

Change of Base: log_b(x) = log_k(x) / log_k(b) [for any base k>0]

Number of digits

Count number of digits in base 10:

• Number of digits of n = ⌊log₁₀(n)⌋ + 1
• Valid when n>0

Count number of digits in binary

• Number of digits of n = ⌊log₂(n)⌋ + 1
• This tells how many bits are needed to represent n in binary.

import math
n = 123456
digits = math.floor(math.log10(n)) + 1 #output 6



import math
n = 18   #10010
bits = math.floor(math.log2(n)) + 1  # Output: 5

import math
n = 123456
digits = math.floor(math.log10(n)) + 1 #output 6



import math
n = 18   #10010
bits = math.floor(math.log2(n)) + 1  # Output: 5

Why does this works?

Every time you multiply by 10, you add a digit: