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

Advertisements

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

Longest Arithmetic Progression

Input: A sorted array of numbers.
Output: The length of the longest arithmetic progression
Problem: We are given a sorted array and we need to find the length of the longest arithmetic progression..
Example: [1, 9, 10, 11, 16, 21, 28, 30, 31], answer=4.
Complexity: Time O(n^2), Memory 0(n^2)

Before reading this article, it’s strongly recommended to take a look at this one, as it describes the basic idea we gonna use in the solution.

The solution will base on a dynamic programming approach, as the problem has a property of optimal substructure – we can build arithmetic progression of length N if we already know one with lenght (N-1).

Let’s consider three indices L, M, R, L < M < R, and let’s use the property describing arithmetic sequence mentioned in the previous article. If we know three indices L,M,R that are in a arithmetic progression, and we know that M, R, Q indices are also in the aritmetic progression, then L,M,R,Q are aslo in arithmetic progression. We will use this property to create dynamic programming solution.

Another thing worth considering is that every pair of elements is a arithmetic progression already, what gives us initialization property of an array.

We will have A[L][M] array, where we will store the longest progression length, starting with L, M. We will process the progression from right to left, trying to find L and R for a fixed value of M. The code may look like this:

int longestProgression(vector<int> iProgression)
{
    int A[iProgression.size()][iProgression.size()];
    int maxLen = 2;
    // initialize last columnt values
    for(int i = 0; i < iProgression.size(); i++)
        for(int j = 0; j < iProgression.size(); j++)
            A[i][j] = 2;

    for(int M = iProgression.size() - 1; M > 0; M--)
    {
       int L = M - 1;
       int R = M + 1;
       while(L >= 0 && R < iProgression.size())
       {
           int LR = iProgression[L] + iProgression[R];
           int M2 = IProgression[M] * 2;
           if(LR > M2)
           {
               L--;
           }
           else if(LR < M2)
           {
               R++;
           }
           else
           {
               A[L][M] = A[M][R] + 1;
               maxLen = max(A[L][M], maxLen);
               L--; R++;
           }
       }
    }
    return maxLen;
}

The complexity of the solution is O(n^2) and the memory is O(n^2) too.

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

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