5.2 KiB
Maths 3 - Modular Arithmetic
Arithmetic of Remainders
x % m
gives a value \in [0, m-1]
Say m = 4
Since 1, 5, 10 have the same modulus, they can be said to be "modular equivalent wrt 5"
0 \equiv 5 \equiv 10 \mod 5
1 \equiv 6 \equiv 11 \mod 5
Linearity of remainders
Remainder of sums is the sum of remainders (modular-sum)
Incorrect: (a+b) \% m = a \% m + b \% m
This is wrong, because (m-1) + (m-1) = (2m-2) can be >= m
Correct: (a+b) \% m = \Bigl ( a \% m + b \% m \Bigr ) \% m
Linearity works for both +ve and negative.
But, we need numbers to be \in [0, m-1]
So, negative modulus values can be fixed by simply adding m
(10 - 4) \% 7
= (10 \% 7 - 4 \% 7) \% 7
= (3 - 4) \% 7
= -1 \% 7
= -1 + 7
= 6
Distributive over multiplication, addition, substraction but not division.
Count Pairs
Given A[N]. non-negative integers. Given m Count number of pairs (i, j), such that a[i] + a[j] is divisible by m
Brute Force: O(n^2)
Example:
A = [2 2 1 7 5 3], m = 4 answer = 5 (2,2), (1, 7), (1, 3), (7, 5), (5, 3)
Optimized: Instead of thinking of remainders of sum, think of sum of remainders.
That is, if I've an element which gives remainder x
, then it can be paired with an element which gives remainder m-x

Keep counts for each remainder. Finally, count the number of pairs
0 - 0 1 - 2 2 - 2 3 - 2 So,
\dfrac{c_0 (c_0-1)}2 + (c_1 \times c_3) + \dfrac{c_2 (c_2-1)}2
= 0 + 4 + 2 = 6
Special cases for remainders is 0, n/2 Note: loop till m/2 so that you don't double count
total = count[0] choose 2
if m % 2 ==0:
total += count[m/2] choose 2
else:
total += count[m//2] + count[m//2 + 1]
for i <- 1 .. m/2-1:
total += count[i] * count[m-i]
Complexity: Time: O(n + m)
Space: O(m)
Count Triplets
Given A[N] with non-negative integers Given m, find the number of triplets such that sum is divisible by m
Think in terms of the last question
Brute Force: O(n^3)
With last approach: O(n + m^2)
- Bucket
- Choose 2 mods: a, b. Third mod c = m - (a+b)
- Count total
- All 3 from same bucket - for 0 and m//3
- 2 from same bucket, one from other bucket
- all 3 from different buckets

So, fix two buckets, so 3rd can be chosen
Enforce two things:
- i <= j <= k otherwise, repetitions can happen
- i + j + k = 0 or i + j + k = m
total = 0
for i <- 0 .. m-1:
for j <- i .. m-1:
k = (m - i + j) % m # explain the case when i, j are 0
# explain that this mod should handle -ve
# python. for c++/java, do it yourself
if i == j == k:
total += count[i] choose 3
elif i == j:
total += count[i] choose 2 * count[k]
elif i == k:
total += count[i] choose 2 * count[j]
elif j == k:
total += count[j] choose 2 * count[i]
else:
total += count[i] * count [j] * count[k]
Time: O(n + m^2)
, Space: O(m)
Balanced Paranthesis Count
Given N pairs of paranthesis Find number of distinct balanced paranthesis
meaning of balanced: for every prefix, number of opening braces should be >= number of closing braces
Example
0 pairs 0
1 pair: () 1
2 pairs: ()(), (()) 2
3 pairs: ()()(), ()(()), (())(), (()()), ((())) 5
Say we want to construct for n = 3 Choose how many pairs must go inside


C_0 = 1
C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots C_{n-1}C_0
\displaystyle C_n = \sum\limits_{i=0}^{n-1} C_i C_{n-i-1}
Catalan numbers
Same as above
Time to find nth catlan number = O(n^2)
(because we need to compute numbers before it)
Number of Paths
Given
m \times n
grid, find the number of paths from (0,0) to (m-1, n-1) Can only move right and down.
Approach:
- Every path will have exactly (n-1) right steps, and (m-1) down steps.
- Only the order differs
So, \dfrac{(n+m-2)!}{(n-1)! \cdot (m-1)!}
Complexity? O(n+m)
Number of lower triangle paths in Square Matrix
Given
n \times n
(square) grid, find the number of paths from (0,0) to (m-1, n-1) Can only move right and down. Exists only in teh lower triangle
- First move must be down
- Number of Rs < Number of Ds at every step
C_{n-1}
, because n-1 pairs of moves for n \times n
matrix