Notes about programming
“Trapping Rain Water” is one more famous algorithm problem using bars, like Skyline Problem or Lagest Rectangle in a Histogram. Compared to other two bar chart problems, this was an easier problem once I understood what I should focus on. Also, solutions are posted on many websites, which helped to solve.
The skyline problem is another famous algorithm problem using bars, like Lagest Rectangle in a Histogram. Although the problem is described using bars, it is totally another problem compared to the largest rectangle. The skyline problem asks range maximum values.
“Find the largest rectangular area in a histogram” is a famous algorithm problem using bars. There are some types of problems expressed by bars such as trapping water or skyline. Those look like similar since all are plotted on 2D plain multiple bars on. However, how to think and solve the problems are not the same. What data structure and algorithm can be applied to solve problems effectively is, sometime, confusing. For this reason, I’m going to add this topic to my memo.
This post is about XOR bit manipulations. XOR is surprisingly capable of solving various algorithm problems.
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.