Find the number of set bits in the result of multiplication of big numbers

You are given a number that might be so big that it doesn’t fit in any standard type, however the number is provided in a form of [a, b, c, d, …] where every letter stands for the bit number that is set in the byte representation, so you can read it easily. In example [1, 3, 4] represents 1101 = 13. Then you multiply the number by 3. How many bits are set to 1 in the binary representation of the result?

This is a real interview question that has been asked to a friend of mine quite recently. To figure out the solution, we need to firstly consider what the multiplication by 3 really means. Let’s take an example.

 01101
x00011
--------
 01101
+11010
--------
0100111

As you can see the result is the sum of the number itself and the number shifted to left by 1. The former is obvious, as it is the result of multiplying by 1. The latter is what multiplication by 2 does. Multiplication by 2^n shifts the byte left by n positions in a general case.

Coming back to our result we get [1, 3, 4] x 3 = [1, 3, 4] << 1 + [1, 3, 4] = [2, 4, 5] + [1, 3, 4]. Now we may answer the question: what bytes will be set after this addition? Recalling the binary arithmetic and we may notice that the solution lays in calculating the result of the addition of the. In simpler words we just need to implement binary addition of numbers represented in the form of [2,4,5] and [1,3,4]. The answer will be the size of the result structure.

int getNumberOfSetBits(vector<int> number)
{
        // calculate the number shifted by 2
        vector<int> shifted = number;
        for(unsigned int i = 0; i < number.size(); i++)
                shifted[i]++;

        bool carry = false;
        vector<int> result;

        // the first element of number will surely be a part of the result
        result.push_back(number[0]);

        // start the addition 
        for(unsigned int i = 1; i < number.size(); i++)
        {
                if(number[i] == shifted[i-1])
                {
                        if(carry)
                        {
                                result.push_back(number[i]);
                        }
                        carry = true;
                }
                else
                {
                        result.push_back(number[i]);
                        result.push_back(shifted[i-1]);
                        carry = false;
                }
        }

        // do not forget the carry the last one from shifted
        int last = shifted.size() - 1;
        if(carry)
                result.push_back(shifted[last] + 1);
        else result.push_back(shifted[last]);

        return result.size(); 
}

The code could be optimized as actually the structure result is not necessary. But it keeps more visible what was the idea behind the algorithm.

Regards

Joe Kidd

Advertisements

Useful sums and formulas

In algorithmic challenges you may very often meet problems that are somehow related to mathematical series, distributions, or combinatorics. As I not always remeber all the formulas I have created a quick reference.

1. Arithmetic Progression and Series

a) Sum
S_n = \frac{n}{2}(a_1 + a_n)
b) N-th element of the progression
a_n = a_1 + (n-1)d
Where r stands for the difference

2. Geometric Progression and Series

a) Sum
S_n = a_1\frac{(1 - r^n)}{1-r}
b) N-th element of progression
a_n = a_1 * r ^ n
Where r stands for ratio.

3. Gauss sum
\sum\limits_{k=1}^n k = \frac{n(n + 1)}{2}

4. Gauss series
\sum\limits_{k=1}^{\infty} (k+1)z^k = \frac{1}{(1 - z)^2}

5. Sum of squares
\sum\limits_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

6. Factorials sum
\sum\limits_{k=0}^{n} k(k+1) = \frac{n(n+1)(n+2)}{3}

7. Binomial theorem
\sum\limits_{k=0}^{n}  \binom {n} {k}x^ky^{n-k} = (x+y)^n

8. Harmonic function
ln( \frac{1}{1-z})= \sum\limits_{k=0}^{\infty}(z^k/k)

In the next article we will summarise probability.

Best Regards

Joe Kidd

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

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

Convert a mathematical expression into RPN

This is a very common technique and actually it has been described in thousand of places. We are given a string representing a mathematical expression, and we are expected to convert it into Reverse Polish Notation what makes evaluation way easier. As an example let’s consider a following expression 2 + 5 * 4 that in a RPN has a form of 2 5 4 * +.

So we have an expression given in an infix notation and we need to convert it to RPN. Not to make the problem to difficult we assume there are no function operators, nor separators and neither unary minus. So basically we have only positive numbers, parenthesis and basic arithmetic operations like +, -, *, /. And what is the most important we assume the expression is correct, so no need to validate (even if it was pretty simple it’s not a part of the problem).

The conversion algorithm has been created by Dijkstra and is called Shunting-yard algorithm. The algorithm uses two data structures, a queue Q and a stack S:

while there are tokens to read
    t = the next token
    if isNumber(t) then Q.push(t)
    if isOperator(t) then
        while isOperator(S.top())
              and priority(S.top()) > priority(t) then
           Q.push(S.pop());
        S.push(t);
    if isLeftParenthesis(t) then
       S.push(t);
    if isRightParenthesis(t) then
       while ! isLeftParenthesis(S.top()) then
          Q.push(S.pop());
       Q.pop()
while S.empty() == false
    Q.push(S.pop());

An interesting part is in the line 6 of this code, where we are considering the order of operations. As we know the operations * and / have higher priority than + and – so they should be executed before. Then we are poping them from the stack and putting into the queue.

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

Find the missing number of an arithmetic progression

We are given an array representing the elements of an increasing arithmetic progression. The arithmetic progression might be described by a formula a_n = a_1 + (n - 1) r , that means that n-th element of it, is a sum of the first element and (n – 1) steps r. We are expected to find the missing number in the array taking an assumption that the first and last element are never missing.

To make the problem more understandable let’s take a following example of an array: [1 3 5 7 9 11 15 17]. W can see that the a_1 = 1, and the r might be calculated by making use of the assumption that the first at the last element are never missing r = \frac{(a_n - a_1)} {(n - 1) } = (17 - 1)/8 = 2. We can just check by taking a deeper look at the table that the missing element is 14. Actually we can just scan the table from left to right and compare consecutive elements and stop when the difference between them is different than expected. It leads to O(n) solution. But it smells like we can go better.

As the progression is increasing and we know the precise formula for the element at n-th position we may apply the famous binary search. We just use the fact that if at the n-th position the element is bigger than expected, then the missing number has to be on the left side of the n-th, otherwise the missing number has to be on the right side. However before approaching the previous test there is a necessity to check the current element and the previous one, as the missing element may lay just between them.

The pseudocode could look like follows:

if array[n/2] - array[n/2 - 1] > r then
// we got a missing element that is array[n/2] - r
if array[n/2] > array[begin] + (n/2 - 1)r
// then we we search left part of the array
if array[n/2] = array[begin] + (n/2 - 1)r
// then consider right part of the array

We could code it as:

int findMissingElement(int array[], int begin, int end, int r)
{
    int m = (end - begin)/2;
    if(array[m] - array[m - 1] != r)
        return array[m] - r;
    if(array[m] > array[begin] + (m - 1) * r)
    {
        return findMissingElement(array, begin, m - 1, r);
    }
    else if(array[m] == array[begin] + (m - 1) * r)
    {
        return findMissingElement(array, m + 1, end, r);
    }
}

The complexity is obviously O(log N).

Best Regards

Joe Kidd

Find 3-elements long arithmetic progression in a sorted array

So we are given an array that is sorted in ascending order, and we are expected to find 3-elements that are arithmetic progression. As the O(n^3) solution is trivial we are expected to find a better one. Obviously the elements are spread in the array, but the order is maintained.

As an example we may consider the array [1, 9, 10, 11, 16, 21, 30] that has the arithmetic progression [1,11,13]. The trick that is going to lead to the O(n^2) solution bases on the property of an arithmetic progression, that says: 3 elements L, M, R are arithmetic progression when L < M < R. and 2 * M = L + R.

Cool! As the array is sorted L lays on the left hand side of M, and R on the right hand side. So for a fixed M, we need to find L and R meeting the condition above. We may firstly fix L = M – 1, and R = M + 1 and the iterate updating the values of L and R according to the following rule:

if array[L] + array[P] > 2 * array[M] then L--
if array[L] + array[P] < 2 * array[M] then P++
if array[L] + array[P] == 2 * array[M] then we have the answer

What leads us to a implementation of O(n^2).

bool hasArithmeticProg(vector<int> array)
{
    if(array.size() < 3)
        return false;
    
    for(int M = 1; M < array.size() - 1; M++)
    {
        int L = M - 1;
        int R = M + 1;
        while(L >= 0 && R < array.size())
        {
            if(array[L] + array[R] == 2 * array[M])
                return true;
            else if(array[L] + array[R] > 2 * array[M])
                L--;
            else R++;
        }
    }
    return false;
}

The problem is not really about finding the arithmetic progression, is rather about efficient way of finding if there are two elements in a sorted array that sum up to a given number. The arithmetic progression is just an extra thing to make it more funny.

Best Regards

Joe Kidd

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