mirror of
https://github.com/dholerobin/Lecture_Notes.git
synced 2025-03-15 13:49:59 +00:00
777 B
777 B
Radix Sort
- sort elements from lowest significant to most significant values
- explain: basically counting sort on each bit / digit
- Stability: inherently stable - won't work if unstable
- complexity:
O(n \log\max a[i])
Sex-Tuples
Given A[n], all distinct find the count of sex-tuples such that
\frac{a b + c}{d} - e = f
Note: numbers can repeat in the sextuple
- Naive:
{n \choose 6} = O(n^6)
- Optimization. Rewrite the equation as
ab + c = d(e + f)
- Now, we only need
{n \choose 3} = O(n^3)
- Caution:
d \neq 0
- Once you have array of RHS, sort it in
O(\log n^3)
time. - Then for each value of LHS, count using binary search in the sorted array in
\log n
time. - Total:
O(n^3 \log n)
- Now, we only need