Important Formulae

must know concepts

• Rolling Hash : https://en.wikipedia.org/wiki/Rolling_hash#:~:text=A%20rolling%20hash%20(also%20known,that%20moves%20through%20the%20input. used in String Hashing and Rabin Karp

Formulae

• Subsets: Total no. of subsets or Power Sets = 2ⁿ

• Sum of all Numbers till n = ( n * (n+1) ) / 2

• Binary Coefficient(Combination) ⏩ (nCr) = n! / (r! * (n-r)!)

• Pascal's Triangle ⏩ (iCj) = i!/(j! - i-j!) __ // here, i= 0->n-1 & j= 0->i Element at row->r & col->c ⏩ (r-1)C(c-1)== (r-1)!/((c-1)! _ ((r-1)-(c-1))!)

• No. of subarrays derived from an array with n elements ⏩ nC2 + n = (n * (n+1) )/2

• No.of subsequence of an array with n elements ⏩ 2^n.

• Fibonacci Sequence ⏩ fib(n) = fib(n-2) + fib(n-1)

• Check Prime No. ⏩ for (int i=2; i<=Math.sqrt(num); i++)

• If given a+b = N then for a = N/2 & b = N/2 a*b will be maximum for given a, b

• gcd(x, x+1) == 1

• Eucledian distance = √((x2 - x1)^2 + (y2 - y1)^2)