Categories
algorithms kotlin

Problem 5.5 from EPI -> Compute X x Y without arithmetic operands

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.

Categories
algorithms kotlin

Problem 5.9 from EPI -> Is number a palindrome?

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.

Categories
algorithms kotlin

Problem 5.11 from EPI -> Intersecting rectangles

Give a rectangle, does another rectangle intersects it? If it does print out the intersecting rectangle!
The tricks to detecting if they intersect is to treat x and y axis separately, and then combine both checks in to one.
The trick to getting the intersected rectangle is to realize that any of the two rectangles can be on the left or the right side, so taking max() and min() of both rectangle we can get a correct answer.
Take a look at this code

Categories
algorithms kotlin

Problem 5.8 from EPI -> Reverse digits of a number

Given a number like “123”, print out the reverse of that number like “321”!
There is a quick and easy way, convert the number to string and call string.reverse(), but it takes more memory than is neccessary.
A better way is to repeatedly take the most right number multiply it by 10 and add the next most right number, repeat until the number to reverse is zero.
Take a look at this code.
Happy coding!