Check if for a given matrix size, you are able to visit every cell


This problem was described in TopCoder SRM 594, but it’s simplification is described above. To sum up, we are given a matrix of size N, M and we need to check if it’s feasible to visit every cell in the matrix, traveling from cell to cell according to a simple rule: from position [i, j] we may go only to [i+1, j+1]. This problem is REALLY cool and strongly encourage you to read the solution when you got here!

The simplest solution would be just to create such a matrix and then start visiting it, until we realize we can’t visit it completely, or we do it. What should be a starting position of such a traversal? As we need to visit all the cells, we may choose randomly any of them as a starting position. However the solution would work, it’s not satisfactory as the complexity is O(M*N), what sucks.

Instead of thinking about the algorithm it would be good to stop here for a while and wonder when the matrix might be fully visited.

Did you really think? Ok, so then surely you know the solution. Anyway I will provide it here for those who cheated. The answer is: when the GCD of M, N is 0. Why? Because in this case the Lowest Common Multiple will be equal to M*N. And add it this information to your heart. What does it mean for us? It means the first element that is going to be visited second time, will be visited after M*N moves. As the size of the matrix is M*N, it means that all the elements of the matrix will be visited before we will reach an element the second time. Otherwise, when we meet an element already visited, before M*N steps we are sure that skipped some cells and we will never reach them, as the traversing methods remains the same.

Best Regards

Joe Kidd

Advertisements

GCD of two numbers when one is very big

On the standard input, we are given two numbers, A and B, where 0 <= B <= 40000 and B <= A < 10^250. We need to find the greatest common divisor of them.

The statement of this problem originally comes from CodeChef pages. The problem itself is very simple, if you know the trick. The well known gcd algorithm is:

gcd(A, B) = gcd(B, A % B)
gcd(A, 0) = A

Yeah, but keep in mind that one number is pretty big and will not fit in a standard type, so the code above is not really useful now. However, we could go for a type like BigInteger, but it’s not really necessary. Let’s imagine that the big number is given as a string for now. We can then construct the integer from the string using iterative approach. When we recall the following property of modulo sum, actually we are home:

(A + B + C + D) \% N = (A\%N + B\%N + C\%N + D\%N)\%N

What leads us to following conversion code:

unsigned int convert(string s, unsigned int b)
{
    unsigned int answer = 0;
    for(int i = 0; i < s.size(); i++)
    {
       answer *= 10;
       answer += s[i] - '0';
       answer = answer % b;
    }
    return answer;
}

Now, if we have the result of covert method, we may use it as a parameter to gcd algorithm.

Best Regards

Joe Kidd

Greatest Common Divisior of a sequence of numbers

It’s well known how to calculate a greatest common divisor of two numbers. But what if we are considering a sequence of them and we are expected to return gcd?

This probably not necessary, but just to keep thing in order the greatest common divisor algorithm might be defined in a following way:

gcd(A, B) = gcd(B, A % B)
gcd(A, 0) = A

The solution of the problem lays in the property of greatest common divisor. The gcd is associative what might be expressed:

gcd([A,B,C,D, ..., Z]) = gcd(gcd(gcd(gcd(gcd(A,B), C) D),...), Z)

A, B, C, D… are some integers. Done 🙂

Best Regards

Joe Kidd

Counting factorials of relatively small numbers

We are given a big number, let’s say 345. It’s not big? It is, try to calculate the factorial. I will present a solution that might be required in the problem, however it’s mainly used for big number multiplication.

This solution is quite tricky but very easy to implement and explain. I think it’s worth being aware of it as it looks simple enough to be a problem for an interview. We may just keep the big number in an array and calculate the multiplication in the way mentioned below. So let’s say we have two numbers A = 345 B = 15, and A is kept in an array A = [5, 4, 3]. Now we multiply in the following way:

carry = 0;
Step 1:
array[0] = (array[0] * B + carry) % 10 =
 (5 * 15 + 0 ) % 10 = 75 % 10 = 5
carry = (array[0] * B + carry) / 10 = 75/10 = 7
Step 2:
array[1] = (array[1] * B + carry) % 10 = 
 (4* 15 + 7 ) % 10 = 67 % 10 = 7
carry = (array[1] * B + carry) / 10 = 67/10 = 6
Step 3:
array[2] = (array[2] * B + carry) % 10 = 
 (3* 15 + 6 ) % 10 = 51 % 10 = 1
carry = (array[2] * B + carry) / 10 = 51/10 = 5

Because carry is greater than zero we need to add it to the array and the result array is [5, 7, 1, 5], what gives a number 5175. Please check if the multiplication result is correct indeed.

Best Regards

Joe Kidd

The length of the longest sequence of 0s in the bit representation

We are given an integer value and we are expected to provide the information about the length of the longest sequence of 0s in its bits representation, but the solution should be not worst than O(log N). In example 167 = 10100111, the answer is 2.

O(log N) for this problem? It’s gonna be freaking tricky outstanding solutions that moves the limits of algorithms up to the boundaries and even a step behind! Let’s take a look at the code firstly and then we will explain what are we doing.

int maxZeroLen(int N)
{
int maxLen = 0;
int curLen = 0;
while(N)
{
int remainder = N % 2;
N = N >> 1;
if(!remainder)
curLen++;
else curLen = 0;
maxLen = max(maxLen, curLen);
}
return maxLen;
}

Yes it is that simple. Sorry if you expected some magic here. When we divide by 2, we actually decrease the size of the problem in the logarithmic fashion 1/2, 1/4, 1/8… etc. So the solution is O(log N). I really like this problem as it makes you think and explains what logarithmic complexity really is.

Best Regards

Joe Kidd

Bit tricks and tricky questions

Those problem pretty often appears in interviews. I had them spread in lot’s of places, so just to order things a little bit I gathered them in one place. On the other hand they are small enough they don’t deserve for a seperate post.

1. Add two numbers without using arithmetic operations.
2. The lowest of three numbers without using comparison
3. Multiply by seven without using multiplication operator.
4. Swap of the numbers without using an extra variable
5. Check if a number is a power of 2

Problem: Add two numbers without using arithmetic operations.

We need to note that XOR of two numbers contains it sum if there is no carry anywhere. I.e

3 = 101
2 = 010
————— XOR
5 = 111

So we may use this property, remembering to consider the carry at every step.

int carry = 1;
// while we don't have carry anymore
while(carry)
{
// so we get all the positions where carry may appears
carry = x & y;
// we got the sum without a carry
x = x ^y;
// we move the carry, one position on the left
// and we try to add again
y = carry << 1;
}

Problem: The lowest of three numbers without using comparison

What about this solution?

while(x && y && z)
{
x--; y--; z--;
c++;
}
return c;

The other solution uses only bit operation what makes it even more interesting. Obviously if we know a way to choose the smallest of two numbers, we can extend it to three of them. For two numbers the solution could be:

// mask will contain only 0s, or only 1s, depending on
// if the difference between x and y is positive
// or negative (check U2 system).
int mask = ((x - y) >> (sizeof(int) * CHARBIT - 1));
// if the mask contained zeros it means that x >= y,
// so (x - y) dissapears.
// if the mask contains only 1s, then the difference
// remains and we get y + x - y = x.
int min = y + (x - y) & mask;</pre>

Problem: Multiply by seven without using multiplication operator.

// multiply by 8
int x8 = x << 3;
int x7 = x8 - x;


Problem
: Swap of the numbers without using an extra variable


a = b - a;
b = b - a;
a = a + b; // because (b - a) + (b - b + a) = b


Problem
: Check if a number is a power of 2


return (N & (N - 1)) == 0;

Find a permutation knowing its rank

Input: A number M, describing a rank of permutation of N elements
Output: Permutation with a given rank
Problem: We are given a rank and we need to find the proper permutation
Example: rank=1 p=123, rank = 2 p=132, rank = 3, p=213, etc.

In this article we have discussed how to find a rank of a permutation. Now let’s try to do the opposite thing: knowing the rank, find the proper permutation.

We will use the idea described in Skiena’s book, “The Algorithm Design Manual” (if you don’t have it yet, go and buy, as it’s a nice source of algorithmic problems and mr. Skiena seems to be a clever guy).

So we have a function Unrank(M, N), that according to the definition of the problem, tries to find what is the permutation at M position, in a permutation of N elements, having some order of generation.

Let me remind the Rank function from the article, that is given in the following way:

Rank(p) = (p_1 - 1) * (|p| - 1)! + Rank(p_2,...,p_{|p|})

How can we revert the permutation from the given rank number? The part (p_1 - 1) * (|p| - 1)! gives us an information how many permutations of size |p| appears, before we got  the value at p_1 at the first position. Then we proceed for the next number by a recursive call. In this case we have to find such a maximum number X for p_1, that there will be at max M permutations in front of him. So the following condition has to to be met:

(X - 1)*(N - 1) !<= M

Getting this number, we are updating ordering, as it was previously described in the rank algorithm and then we proceed for a problem with smaller size.

Let’s take an example to see if we correctly understand the problem. Let’s say we are looking for M = 3, N = 3.

Step 1.


Unrank(3, 3):
Ordering [1,2,3] => [1,2,3]
X = 3, then (3 - 1) * (3 - 1)!  = 4 > 3, condition not met
X = 2, then (2 - 1) * (3 - 1)! = 2 <= 3, condition met, so p1 = 2
Update the ordering removing 2, we [1,2,3] => [1,x, 3 - 1] = [1,2]

Step 2.

Unrank(1, 2):
Ordering [1,3] => [1,2]
X = 2, then (2 - 1) * (2 - 1)!  = 1 <= 2, condition ment, so p2 = 3
Update the ordering removing 2, we [1,2] => [1,x] = [1]

Step 3.

Unrank(0, 1):
Ordering [1] = [1]
As we are looking for 0 element for 1 element ordering it will be
exactly this element, so p3 = 1

So the given permutation is p = [2, 3, 1] and using rank algorithm we can really check that this answer is correct. The M parameter also changes with the recursion. If we figured out that the element with rank Y should be used, then in the next step M = max(M – Y, 0).

Best Regards

Joe Kidd

Check if a number is a power of 4

Input: A number N
Output: True if N is a power of 4, False otherwise
Problem: We are given a number, and we need to check if it’s a power of 4
Example: 64, result = True
Complexity: Time O(log log n), Memory 0(1)

This problem is very trivial and basically we could solve it, in a iterative way, just checking consecutives powers of four and compare them against N. But if it were that simple, it wouldn’t appear here. Moreover we have a complexity limit that is O(log log n). Checking every power of 4 would be efficient, especially if we would use bit shifting instead of normal power, but not efficient enough, as we would get O(log n) solution.

Before we will discuss the real solution let’s take a look at the binary representation of powers of 4.

4^0 = 0000001
4^1 = 0000100
4^2 = 0010000
4^3 = 1000000

As we can see the bit is set only at the odd positions and only once. How can check this condition in a effective way? We can use a powerful binary search again.

1. We divide the number bit representation into two pieces.
2. Only one piece might be not zero, if this condition is not met, the number is not a power of 4.
3. Choose a non zero part and go to step 1. as long as you find number 1, then go to step 4.
4. Check if the bit is on the odd position, if not return false, as the number is not a power of 4 otherwise go to step 5.
5. Flip the bit from the step 4, if the number euqals zero now, it is a power of 4 , otherwise it’s not.

This algorithm would give us the expected O(log log n) complexity.

There is also another solution, that is way easier to implement and works in O(1) time. As we can see from the example above, the bits are set on the odd positions. But let’s go in a opposite way and think about even positions. We know, that no even position might be set. Secondly we know that power of 4 is also a power of 2. If this condition are met, then we have a power of 4 number.


bool isPowerOf4(int N)
{
int mask = 0xAAAAAAAA; // mask with set values at the even position
return (N & mask == 0) && (N & (N - 1) == 0);
}

This solution is prettier, but I like more the one with binary search ans it shows an interesting application of this algorithm.

Best Regards

Joe Kidd