Solution To "An Unusual Sorting Algorithm"

View Problem: An Unusual Sorting Algorithm

It is easy to see that the position of the number x in the final sorted array should be x. It it also clear form the algorithm that the operation for every i is essentially swap(i, A[i]), meaning swap the numbers at indices i and A[i]. This means, the value at A[i] eventually becomes A[i]. So, in one iteration of the while-loop, for all i in [1..N], we attempt to correctly place A[i] in it's correct position which is A[i]. Let us look at an example:

A = {4,3,1,2}

1st iteration -

i=1: swap(1,A[1]) = swap(1,4). So, A = {2,3,1,4} // Correctly placing 4
i=2: swap(2,A[2]) = swap(2,3). So, A = {2,1,3,4} // Correctly placing 3
i=3: swap(3,A[3]) = swap(3,3). So, A = {2,1,3,4} // Correctly placing 3
i=4: swap(4,A[4]) = swap(4,4). So, A = {2,1,3,4} // Correctly placing 4 

2nd iteration -

i=1: swap(1,A[1]) = swap(1,2). So, A = {1,2,3,4} // Correctly placing 2
i=2: swap(2,A[2]) = swap(2,2). So, A = {1,2,3,4} // Correctly placing 2
i=3: swap(3,A[3]) = swap(3,3). So, A = {1,2,3,4} // Correctly placing 3
i=4: swap(4,A[4]) = swap(4,4). So, A = {1,2,3,4} // Correctly placing 4 

The array A is now sorted.

However while placing A[i] in its correct position, we may fail to place A[A[i]] in its correct position, as, clearly, placing A[A[i]] at i does not guarantee that it has been placed correctly. This can be noticed in the above example. When we perform swap(1,4) in the 1st iteration, we place 4 at position 4 but we place 2 at position 1.

At every i, we place one element correctly in its position. However, we may be trying to place an already correctly placed element in the same position. This can be observed at i=3 and i=4 in the 1st iteration of our example. Hence, clearly, we may need more than one iterations for sorting array A.

With this insight, let us now try to derive a worst-case complexity for sorting array A. Let us represent array A with R's and W's. An 'R' at position i means the element at this position is "Rightly" placed. A 'W' at position i means the element at this position is "Wrongly" placed.

A = {4,3,1,2} // {W,W,W,W}

1st iteration -

i=1: swap(1,A[1]) = swap(1,4). So, A = {2,3,1,4} // {W,W,W,R}
i=2: swap(2,A[2]) = swap(2,3). So, A = {2,1,3,4} // {W,W,R,R}
i=3: swap(3,A[3]) = swap(3,3). So, A = {2,1,3,4} // {W,W,R,R}
i=4: swap(4,A[4]) = swap(4,4). So, A = {2,1,3,4} // {W,W,R,R} 

2nd iteration -

i=1: swap(1,A[1]) = swap(1,2). So, A = {1,2,3,4} // {R,R,R,R}
i=2: swap(2,A[2]) = swap(2,2). So, A = {1,2,3,4} // {R,R,R,R}
i=3: swap(3,A[3]) = swap(3,3). So, A = {1,2,3,4} // {R,R,R,R}
i=4: swap(4,A[4]) = swap(4,4). So, A = {1,2,3,4} // {R,R,R,R} 

The array A is now sorted.

Clearly, swapping two W's replaces at least one of these two W's with R. Also, if we come across an R, it makes no difference (and hence no value-addition towards sorting) at all.

Our goal is to convert array A from N W's to N R's. Since two W's in the worst case produce one R in a single iteration, half of the wrongly placed array gets rightly placed. Hence, we can now say that the while-loop runs at most O(logN) number of times. So, the complexity of our algorithm is O(NlogN).

To create an array which gets only half sorted in every iteration, we use the following strategy. We try to ensure that all the R's get created at the right-end of the array, and, exactly half the W's get converted to R's. So, an ideal array A for N = 2 will be A = {2,1} so that it takes at least one iteration to sort it. For N=4, we have to ensure that it takes 2 iterations. Since our original array for N = 2 is {2,1}, our desired array A at the end of 1st iteration for N = 4 should be A = {2,1,3,4}. This would mean our original array A to be A = {4,3,1,2}.

After applying this strategy, let us create an array for N = 8. Since our original array for N = 4 is {4,3,1,2}, we would like our desired array for N = 8 at the end of 1st iteration to be A = {4,3,1,2,5,6,7,8}. To find our original array for N = 8, we let the first half be {8,7,6,5} and the second half to be Invert(Original array for N=4), so that the desired array plays out for us as intended. Hence, for N = 8, original array A = {8,7,6,5,2,1,3,4}. A similar strategy can be applied for any general N.

Squary Numbers

A number is said to be Squary if it can be partitioned in a way such that each partition is a perfect square. For example, the numbers 164 and 4036729 are Squary numbers because they can be partitioned into (1,64) or (16,4) and (4,0,36,729) respectively. However, the number 139 is not Squary. Let us see all the possible ways or partitioning 139 -

All possible ways of partitioning 139 -

(139)
(1,39)
(13,9)
(1,3,9)

Hence, 139 is not a Squary number.

As we can see in the above example, no case exits in which all the partitions are perfect squares.

Given a number N, can you efficiently find out if it is Squary or not? If it is Squary, can you give any one valid partitioning for this number?

View Solution: Solution to "Squary Numbers"

Multiplying Nines

We are given two numbers A and B, both only comprising of the digit 9. A has N 9's and B has M 9's. For example, if A has 4 9's and B has 3 9's, then A = 9999 and B = 999.

Given N and M, can you find the value of (A x B) without actually multiplying them?

Shown below are some examples to tickle your grey cells -

9 x 9 = 81
99 x 9 = 891
99 x 99 = 9801
999 x 9 = 8991
999 x 99 = 98901

View Solution: Solution to "Multiplying Nines"

Divided Tree Processing

A system consists of N processors numbered [1..N] and arranged in the form of a tree, rooted at processor 1. Each processor has either 2 or zero child processors.

The main job of the system is to complete a given task. The system completes the task in the following manner -

1. At the very beginning, i.e. at time T = 0, the task is given to processor 1.
2. Processor 1 divides the task into 2 equal parts and gives one part each to its child processors. Before giving away the sub-tasks to its child processors, it may wait for some integral amount of time. For example, it may give away the sub-task to its first child at T = 2 and the sub-task to its second child at T = 5.
3. Once the children receive their tasks, they too carry out a similar procedure as the one carried out by processor 1.
4. This goes on recursively.
5. If a particular processor does not have any children, it completes the entire task by itself and returns the result without any delay to its parent processor.
6. Once a parent processor receives the sub-results from both its child processors, it merges these two sub-results and returns the overall result without any delay to its parent processor.
7. However, a parent processor cannot receive sub-results from both its child processors at the same time. If it does, the whole system will crash. This means, if a parent processor receives a sub-result from one of its child processors at time T=t, then it can receive the sub-result from its other child processor only at times T = t+1, t+2, t+3, .. and so on.
8. Note that if a child processor wants to return its sub-result to its parent, the parent has to accept it immediately without any delay.
9. The time taken to complete a task, to merge 2 sub-tasks or to give away sub-tasks to child processors is negligible.

Some examples are shown below. The numbers in red indicate the time at which the processor recieved the task. The numbers in green denote the time at which the processor completed the task.

Example 1

Example 2

Given a tree as mentioned in the statement, can you state the minimum time taken by the system to complete a given task? Also give the times at which each processor received the task and the times at which each processor completed its task.

View Solution: Solution to "Divided Tree Processing"

Sum of Digits

Say we have 2 numbers abc and def, where, a, b, c, d, e and f are the digits of the 2 numbers lying in [0..9]. Adding these 2 numbers gives us the number ghij. Again, g, h, i and j are the digits of the resulting number.

  abc
+ def
----------
 ghij

Can you prove that

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

is always true?

To understand better, let us see an example -

  379
+ 822
----------
 1201

(3 + 7 + 9 + 8 + 2 + 2) % 9 = 31 % 9 = 4
(1 + 2 + 0 + 1) % 9 = 4 % 9 = 4

Let us now generalize the above statement. Say we have N numbers A₁, A₂, ... A_N. Let S(x) denote the sum of digits of the the number x.

Can you prove that

[S(A₁) + S(A₂) + .. + S(A_N)] % 9 = S(A₁ + A₂ + .. + A_N) % 9

is always true?

To put it in a single sentence, can you prove that the sum of digits of a group of numbers modulo 9 is the same as the sum of digits of the sum of those numbers modulo 9 ?

View Solution: Solution to "Sum of Digits"

Splendid Matrices

A Splendid Matrix of order N is a special kind of matrix having dimensions 2^N X 2^N filled in a specific manner. Splendid Matrices of order 1, 2 and 3 are shown below-

Splendid Matrix of order 1

1   2
3   4


Splendid Matrix of order 2

1   2   5   6
3   4   7   8
9   10  13  14
11  12  15  16


Splendid Matrix of order 3

1   2   5   6   17  18  21  22
3   4   7   8   19  20  23  24
9   10  13  14  25  26  29  30
11  12  15  16  27  28  31  32
33  34  37  38  49  50  53  54
35  36  39  40  51  52  55  56
41  42  45  46  57  58  61  62
43  44  47  48  59  60  63  64

Can you state an algorithm to construct a Splendid Matrix of order N? 

Without constructing a Splendid Matrix of order N, how would you go about finding the location (i.e. the row and column nos. of the matrix) of a given value in [1..4^N]. 

Conversely, given a location i.e. a row and column no. pair (R,C) such that R and C lie in the interval [1..2^N], how would you find the value at that location, again, without constructing the matrix?

View Solution: Solution To "Splendid Matrices"