Problem: Given a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j. Hint :- If the average of two numbers is not
The right solution is follow:
Let’s say you started with 1 2 3 4 5 6 7 8 9 10 11 12.
1 2 3 4 5 6 7 8 9 10 11 12 ->
2 4 6 8 10 12 (0 mod 2) | 1 3 5 7 9 11 (1 mod 2) ->
4 8 12 (0 mod 4) | 2 6 10 (2 mod 4) || 1 5 9 (1 mod 4) | 3 7 11 (3 mod 4) ->
8 (0 mod 8) | 4 12 (4 mod 8) || 2 10 (2 mod 8) | 6 (6 mod 8) ||| 1 9 (1 mod 8) | 5 (5 mod 8) || 3 11 (3 mod 8) | 7 (7 mod 8).
Now all the partitions are size 2 or smaller, so we’re done. The final result is 8 4 12 2 10 6 1 9 5 3 11 7. I invite you to verify that all constraints are satisfied.
Here, I want to write why it use the modulo.
Let’s consider about some numbers which the modulo is 8( x, which x mod 8 = 7): 7, 15, 23, 31, 39, 47, 55
Because all modulo of each number is 7, there is probability that average of 2 numbers are still in this group. (7+7)/2=7
For example ( 15 + 31 ) / 2=23, 23
in another way, it is ( 8+7 + 3*8+7) /2 = (2*8+7), (2*8+7) mod 8 = 7, so there is still chance that average of 2 numers is still in this group.
So, we need to break this group into new 2 groups. Let’s those numbers modula 16, then the modulas are:
7 15 23 31 39 47 55
7 15 7 15 7 15 7
Divide them into 2 groups according to new modula: 7 23 39 55, 15 31 47
In this way, any x in [7, 23, 39, 55], and any y in [15, 31, 47], (x+y)/2 mod 16 won’t be 7, nor 15.
For example, (55+47)/2 mod 16 = (16*3+7 + 16*2+15)/2 mod 16.
The idealism is that 16 can be removed, it will be like (7+15)/2 mod 16 = 11( the 2 groups are value of mod 7 or 15)
So, we say average of 2 numbers in different group, won’t exist in either group.