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.

Categories
algorithms kotlin

Problem 5.4 from EPI -> Closest integer with the same weight

This seems like a greedy problem but its quite simple. Look at a place where you can swap 1 and 0 in the given number, the right most the location is the smaller difference will be, that is why the right most is called the least significant bit. So go from right to left and the moment you encounter two bits that differ swap them, take a look at a solution here.

Categories
algorithms kotlin

Problem 5.3 from EPI -> Reverse bits

This one is similar to computing a parity, since we need to check every bit, we can build a cache of already solved parts and just return from cache a solution exists. The key to the solution is to think about what a reverse means, it is basically last two bits reversed will be the first two bits, and second last two bits reversed will be next two bits, etc. Check out the solution here.

Categories
algorithms kotlin

Problem 5.1 from EPI -> Compute parity of a word

The solution I present here is not a complete solution, in the book there is log(n) solution which exploits the 32 bit CPU xor and shift operation. Here I am implemented the second best option which has a time complexity of (N/L), n is the word size while l is the cache size. The trick to this solution is to use a mask which can help you to extract bits, once that is done use a cache which will have an index and a value, value will be the parity of that index. While we are calculating the cache we also calculate the parity in a variable called result. Take a look at the solution here.

Categories
algorithms kotlin

Problem 5.2 from EPI -> Swap bits

The problem 5.2 is quite simple, it asks for bit swapping, so we need to check if i-th or j-th bit are different, if not no need to swap, if they are then just xor the number with 1 shifted left by i bits and 1 shifted left by j bits. Take a look at the code here.

Categories
algorithms kotlin

Problem 5.6 from EPI -> Compute X.div(Y)

Compute a quotient given x and y without using division. The brute force solution would be to keep deducting y from x until x is less then y, but as always there is a better way. Reverse the operation, make it a multiplication operation, first find out which power of 2 times y is less or equal to x, then deduct that from x, while adding that power of two to the result. Running complexity is 0(n), take a look at the code here.

Categories
algorithms kotlin

Problem 5.7 from EPI -> Compute X.power(Y)

This problem can be done in a brute force way by multiplying a number by itself y times. But there is a better approach, keep squaring X value and observing Y least significant bit, if y’s lsb is 1 take x value, bit-shift y value by 1 each time. This approach is faster since bit-shifting will converge to zero faster than doing y times squaring of the x value. Take a look at the code here.