Categories
algorithms EPICh6 kotlin

Problem 6.4 from EPI -> Advance through an array

This problem is quite interesting, at first I thought the only solution to this is using recursion or some sort of graph traversal algorithm. But the problem is much simpler than that if you think about it, we don’t care for all possible paths, we just wan to know if end is reachable. So an easier way is to just keep the maximum index we can reach, and check at the end if we reached last index. How to calculate the next maximum index? nodeMax = i + A[i]. Check out the solution here.

Categories
algorithms EPICh6 kotlin

Problem 6.2 from EPI -> Increment an arbitrary precision decimal number

This one is very cool, what if you have to implement a plus one operation to a very large number, in most languages you have that like in Java there is a BigInteger, but what if you have to write it in c++? Then you would implement your own addition, so the problem requires to implement +1 operations, which can be easily transformed into two number addition, check out the solution here.
I have also added a solution for the variation of problem 6.2. The variation requires addition of two strings that contain binary representation of two numbers. The solution is not that difficult, there is this hard coded version and a more elegant version with bitwise operations, check out the solution here.

Categories
algorithms EPICh6 kotlin

Problem 6.1 from EPI -> Variants 1,2,3

In the first variant of the problem 6.1 we have to sort an array such that all items with the same categories are grouped. If you think about it, this is the same as the pivot partition, check out the solution here.
Second variant is a bit more difficult, we need to group items that can fall into one of four categories. I used the same technique that can sort three categories but with a twist, we keep an index of group two right most item and group three left most item. When they cross it means we have solved the problem. We iterate through the array from the beginning and the end (in the three categories variant we need to just look at the items from the beginning), and keep incrementing end index (category three left most index) and beginning index (category two right most index). Check the solution here.
Third variant is quite simple, items can fall into one of two categories, we need to group them. This is easier than variant 1, we just keep an index for right most category 1 item and left most index for category 2 items and move new items into those categories. When those two indexes reach we are done. Check out the solution here.

Categories
algorithms EPICh6 kotlin

Problem 6.1 from EPI -> National Duch flag

So this one is interesting, the problem requires you to perform a crucial part of a quick sort algorithm the pivot ordering. Basically you need to pick a pivot, and move all elements that are less then the pivot to the left side of an array and bigger elements to the right side of the array. This can be done in various complexities as shown here in code. The trick with this problem is to realize you can make multiple passes for an array, it does not increase the complexity of the solution, so instead of sticking with one pass, break the algorithm into stages, and perform simpler algorithms in each stage. Those simpler algorithms combined will have a solution that works.