Notes about programming

K Partition Problem

Let’s think how we can divide an array of integers into K fair amount groups. The problem description is: given an array of integers, divide into k subarrays so that the differences of sum of each subarray will be minimized. Keep the order of the given array.

Count Smaller By BST

Let’s count smaller on the right in an array. More precisely, the problem is: given an array of integers, count integers smaller than the index i, also, located on the right of index i. So, the answer will be also an array of the integers. Apparently, the answer to the last element is 0.

String Match

The topic here is string search algorithm and not a regular expression. For example, find the position(s) of matched patterns in a loooong text.


Well, how bad naive implementation of generating permutation? Permutation is a well-known problem in mathematics as well as programming. If a set of three characters, {A, B, C}, its permutation is:

Digital Root

What is digital root? Suppose you are given some digits, say 123456, the digital root will be calculated like this: