Solution to "Multiplying Nines"

View Problem: Multiplying Nines

The trick lies in writing a number with K 9's (i.e. 999...9 occurring K times) as 10^K-1. So, the numbers A and B can be written as A = 10^N-1 and B = 10^M-1.

A x B = (10^N-1) x (10^M-1) = 10^N+M - 10^N - 10^M + 1

Without loss of generality, let N >= M. Let us now try to compute the above result:

   10000...0000     // N+M 0's
-     1000..000     // N 0's
-       100..00     // M 0's
+             1
-------------------------------------------------------------
[(M-1) 9's]  [1 8]  [(N-M-1) 9's]  [1 9]  [(M-1) 0's]  [1 1]
-------------------------------------------------------------

The answer can obtained by making simple observations while performing the subtractions and addition as shown above.

Solution to "Divided Tree Processing"

View Problem: Divided Tree Processing

Initially, let us assume that the task can be completed in 0 time. This would mean that each parent assigns sub-tasks to its children at the same time which is T = 0. We will now delay the sub-task distribution only where it will be required, thus minimizing the time to complete the task.

Let time_received[i] denote the time at which node i received its task. Let time_completed[i] denote the time at which node i completed its task. If node i has children, let child[i][0] and child[i][1] denote the indices of its children.

Let us say that both the children complete their tasks at the same time. This case has to be avoided, so we simply delay the giving away of sub-task for one of the children by 1 time unit. This will work due to our initial assumption that all parents distribute the sub-tasks to their children at the same time. We then apply this condition recursively (assume initially for all i, time_received[i] = time_completed[i] = 0):

calculate(i)
{
    if(!hasChildren(i))
    {
        time_received[i] = 0;
        time_completed[i] = 0;
    }
    else
    {
        calculate(child[i][0]);
        calculate(child[i][1]);

        if(time_completed[child[i][0]] == time_completed[child[i][1]])
        {
            /*
             Increment by 1 the time_received[i] and time_completed[i] for all i 
             such that node i belongs to the sub-tree rooted at node child[i][1].
            */

            time_completed[i] = time_completed[child[i][0]] + 1;
        }
        else
        {
            time_completed[i] = max(time_completed[child[i][0]], time_completed[child[i][1]]); 
        }
    }
}

calculate(1) fills time_received[i] and time_completed[i] for all i. time_completed[1] gives us the minimum time taken by the system to complete the entire task.

The above algorithm can be optimized. Instead of incrementing the values of time_completed[i] and time_received[i] for all i which belong to the sub-tree rooted at node child[i][1], we can store separately for which sub-tree the increment has to be performed. In the end, these stored values can be added in a cumulative fashion by following a top-down approach.

Solution to "Sum of Digits"

View Problem: Sum of Digits

The value of the number abc is equal to 100*a + 10*b + c. Similarly, the value of def is equal to 100*d + 10*e + f. Adding these two gives us 100*(a+d) + 10*(b+e) + (c+f), which is the value of ghij. Let us try to represent g, h, i and j in terms of a, b, c, d, e and f:

Case 1: (a+d) < 10, (b+e) < 10, (c+f) < 10

For this case,

• g = 0
• h = a+d
• i = b+e
• j = c+f

So, g + h + i + j = a + b + c + d + e + f. Hence (a + b + c + d + e + f) % 9 = (g + h + i + j)%9

Case 2: (a+d) >= 10, (b+e) < 10, (c+f) < 10

For this case,

• g = 1
• h = (a+d)%10
• i = b+e
• j = c+f

If we prove that (a + b + c + d + e + f - (g + h + i + j)) % 9 = 0, we are done.

  (a + b + c + d + e + f - (g + h + i + j)) % 9 
= (a + b + c + d + e + f - (1 + (a+d)%10 + b+e + c+f)) % 9
= (a + d - 1 - (a+d)%10) % 9
= (10-1) % 9 //(a+d)-(a+d)%10 = 10 as a, d lie in [0..9] so (a+d) lies in [0..18]
= 9 % 9
= 0

Hence proved for this case.

Similarly, the proof can be continued for all cases, and generalized as well.

Solution to "Splendid Matrices"

View Problem: Splendid Matrices

For any Splendid Matrix of order N, we can divide it into 4 equal parts:

• The top left part A[1..2^N-1][1..2^N-1] contains numbers in the interval [1..4^N-1]. 
• The top right part A[1..2^N-1][2^N-1+1.. 2^N] contains numbers in the interval
  4^N-1 (offset) + [1..4^N-1]. 
• The bottom left part A[2^N-1+1..2^N][1..2^N] contains numbers in the interval
  2*4^N-1 (offset) + [1..4^N-1]. 
• The bottom right part A[2^N-1+1..2^N][2^N-1+1..2^N] contains numbers in the interval
  3*4^N-1 (offset) + [1..4^N-1]. 

All 4 parts follow a similar pattern of arrangement of the numbers, except for the offsets.

We try to fill the matrix recursively. Assuming we know the value of the top-left corner element in our matrix (say v), the top left corner row and column pair being (r, c), we can write the following recursive algorithm to fill the matrix (let the matrix be A[1..2^N][1..2^N]) :

fill_matrix (v, r, c, N)
{
    if(N == 0)
    {
        A[r][c] = v;
    }
    else
    {
        fill_matrix (v, r, c, N-1);
        fill_matrix (v+4^(N-1), r, c+2^(N-1), N-1);
        fill_matrix (v+2*4^(N-1), r+2^(N-1), c, N-1);
        fill_matrix (v+3*4^(N-1), r+2^(N-1), c+2^(N-1), N-1);
    }
}

fill_matrix(1, 1, 1, N) generates our Splendid Matrix of order N.

Searching for an element K in the matrix can also be performed in a similar recursive fashion. We divide the matrix into 4 equal parts. Since each part represents an interval of numbers, we need to search only in one of them, which can be selected based on the intervals these parts represent. In every step of the recursion, we maintain the top-left corner element v of our current matrix. The below function assumes that the input will be a legal one, i.e. K lies in [1..4^N].

search (K, r, c, v, N)
{
    if(N == 0) // this also means that v = K.
    {
        return (r, c);
    }
    else
    {
        if(v <= K && K < v+4^(N-1))
        {
            return search (K, r, c, v, N-1);
        }
        else if(v+4^(N-1) <= K && K < v+2*4^(N-1))
        {
            return search (K, r, c+2^(N-1), v+4^(N-1), N-1);
        }
        else if(v+2*4^(N-1) <= K && K < v+3*4^(N-1))
        {
            return search (K, r+2^(N-1), c, v+2*4^(N-1), N-1);
        }
        else if(v+3*4^(N-1) <= K && K < v+4^N)
        {
            return search (K, r+2^(N-1), c+2^(N-1), v+3*4^(N-1), N-1);
        }
    }
}

search(K, 1, 1, 1, N) gives us the correct answer.

In Binary Search, we divide the array into 2 equal parts and search in one of them. Since in this case we are dividing the matrix into 4 equal parts and searching in one of them, we can call it Quaternary Search.

To find the value at a particular (R, C), we again perform a similar recursion as the one above. Only difference will be that we will find out in which of the 4 parts (R, C) lies, and depending on that, we add a certain amount to our answer. When we finally reach (R, C), we have added an appropriate amount and hence we obtain the value at (R, C).

val (R, C, i, j, v, N)
{
    if(N == 0) // this also means i = R and j = C
    {
        return v;
    }
    else
    {
        if(R <= i+2^(N-1) && C <= j+2^(N-1))
        {
            return val (R, C, i, j, v, N-1);
        }
        else if(R <= i+2^(N-1) && C > j+2^(N-1))
        {
            return val (R, C, i, j+2^(N-1), v+4^(N-1), N-1);
        }
        else if(R > i+2^(N-1) && C <= j+2^(N-1))
        {
            return val (R, C, i+2^(N-1), j, v+2*4^(N-1), N-1);
        }
        else if(R > i+2^(N-1) && C > j+2^(N-1))
        {
            return val (R, C, i+2^(N-1), j+2^(N-1), v+3*4^(N-1), N-1)
        }
    }
}

val(R, C, 1, 1, 1, N) gives us the correct answer.