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.

# Category: kotlin

all posts that relate to kotlin

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.

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.

## 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.

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.

## 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.

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.

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.

This one is an interesting problem, the difficulty here is to compute a multiplication with only bitwise operations, so how can this be done?

First we need to figure out how many times we need to add y to x, this can be done by checking how many bits of x are 1, and for each we add shifted y to the sum.

There is also a problem of addition, addition is done with simple bit by bit checking and carry out bit.

Check the complete solution here.

Given a number, check if it is a palindrome or not, for example 121 => true, 122 => false, 2 => true.

There is an easy way, convert the number to string then reverse the string, if both strings are equal it is a palindrome, however that solutions takes up more space, to solve this problem in O(1) space take a look at this solution here. It basically checks how many digits a number has, then repeatedly takes the left most right digit and the right most digit and compares the two, if they don’t match at any step, return false, otherwise return true.